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 vertices.

Let be a threshold graph. One can see, by ordering the vertices in the same way they are given in the *creation sequence*
, where , that the adjacency matrix of is

After computing the eigenvalues of a threshold matrix for
given
and
,
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 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.

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

Joao Batista Carvalho 2015-05-28