Partial Threshold Graphs

Chain graphs and threshold graphs play a very important role in Spectral Graph Theory, since the maximizers for the largest eigenvalue of the adjacency matrix (for graphs of fixed order and size, either connected or disconnected) belong to these classes (threshold graphs in the general case, and chain graphs in the bipartite case). Nesting in the neighborhood of vertices in these graphs has gained the attention of various researchers. Motivated by this structure, we generalize and define a new class of graphs named it as ’partial threshold graphs’ and study the properties. In this article, we give bounds and expressions for the Wiener index and Hyper-Wiener index of a partial threshold graph. We extend the study further and give a set of integers, except which every other integer is the Wiener index of some partial threshold graph. The highlight of the article is an algorithm for the inverse Wiener index problem of partial threshold graphs.