Eigenvalue computation for threshold graphs

Threshold graphs were introduced by Chvátal and Hammer [1] and Henderson and Zalcstein [2] in 1977. They are an important class of graphs because of their numerous applications in diverse areas which include computer science and psychology and we refer to [3] for a more complete account. A threshold graph can be characterized in many ways. We are going to use the characterization by means of its creation sequence of zeros and ones, which reproduces a recursive construction of the graph. This construction starts with an isolated vertex (the creation sequence starts with 0); next, recursively, either an isolated vertex can be added, for a 0 in the creation sequence, or a dominant vertex (adjacent to all previous vertices) can be added, for a 1 in the creation sequence. The process goes on until the graph has $n$ vertices.

Let $G$ be a threshold graph. One can see, by ordering the vertices in the same way they are given in the creation sequence $\{b_1,b_2,b_3,\dots,b_n\}$, where $b_1=0$, that the adjacency matrix of $G$ is

$$A = \left[ \begin{array}{cccccc} 0 & b_2 & b_3 & b_4 & \dots... ...\\ b_n & b_n & b_n & b_n & \dots & 0 \\ \end{array} \right].$$ (1)

where each $b_i$ is either $0$ or $1$, depending whether the $i$-th vertex is isolated or dominant, respectively. The corresponding Laplacian matrix has the form

$$L = \left[ \begin{array}{cccccc} d_1 & -b_2 & -b_3 & -b_4 & ... ...b_n & -b_n & -b_n & -b_n & \dots & d_n \\ \end{array} \right]$$ (2)

After computing the eigenvalues of a threshold matrix for given $\alpha_i, i=1,\dots,n$ and $\beta_i, i=1,\dots,n-1$, computation of some well-know definitions of graph's energy, as well as the computation of the algebraic connectivity of the graph, which is usually defined to be the numerical value of the second smallest eigenvalue of the matrix $L$ above, can be done. In literature, the magnitude of algebraic connectivity is reported to reflect how well connected the overall graph is, and has been used in analysing the robustness and synchronizability of networks.

You can now run a script to investigate changes in energy and algebraic connectivity as you modify threshold graphs of a chosen size.

1. V.Chvatal and P.Hammer, Aggregation of inequalities in integer programming . Ann Discrete Mathematics, 1, 145-162, (1977).
2. P. Henderson and Y. Zalcstein, A graph-theoretic characterization of the pv class of synchronizing primitives. SIAM Journal on Computing, 6, 88-108, (1977).
3. N. Mahadev and U. Peled, Threshold graphs and related topics. Elsevier, (1995).