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.