Isospectral graphs

The secular condition (11) has to be obeyed separately for the leading orders in e. The diverging term implies that (p,0 = (4> 1, (pi, (ps, 0. The term proportional to e requires (po = —Ao4>i. The remaining condition can be expressed as (—AiAq 1 + Ao)(po = 0. This condition, in turn, can be reformulated for vectors of dimension 5 obtained from (po above by disregarding the second and fifth components. The resulting 5x5 matrices for the two isospectral graphs are... 

The main disadvantage of (15) is that the number of directed bonds 2B may be quite large, (in the example discussed presently, 2B = 30 while the matrix A has dimension 7. However, the tree structure of most of the isospectral graphs under consideration here can be used to obtain a much simplified, and almost explicit form of the secular function. This simplification is the object of the present appendix. 

The characteristic polynomial is a molecular descriptor able to discriminate well among several graphs however, some nonisomorphic graphs have the same characteristic polynomial (same eigenvalues), and for this reason they are called isospectral graphs [Herndon, 1974a]. Moreover, the sum of the coefficients of the characteristic polynomial can be used as a scalar molecular descriptor. 

Balasubramanian, K. and Basak, S.C. (1998). Characterization of Isospectral Graphs Using Graph Invariants and Derived Orthogonal Parameters. J.Chem.Inf.Comput.Sci., 38,367-373. 

Characterization of isospectral graphs using graph invariants and derived orthogonal parameters. 

However, there is not a one-to-one correspondence between a graph and its characteristic polynomial, and this has been the subject of investigation of several authors 59-68). Non-identical graphs can possess the same spectrum. These are so called isospectral graphs. The simplest examples of such graphs interesting for chemists are... 

If two nonisomorphic graphs Ga end Gt have equal characteristic polynomials we say that Ga and Gh are isospectral Examples of isospectral graphs are well known (and were first observed by Cdlatz and Sinogowitz [16]). The smallest two such graphs are G i and G 2i... 

I.4. Theorem (Schwenk). fbr arbitrariiy large values of k, there exist coUections of k mutually noni morphic but mutually isospectral graphs. 

Babid D, Gutman I (1992) On Isospectral Graphs. J Math Chem 9 261... 

FIGURE 2.21 A classical example of a pair of isospectral graphs. 

W.C. Herndon and M.L. Ellzey Jr., The construction of isospectral graphs, MATCH Commun. 

Hosoya (2013) and Hosoya et al. (1994, 2001) observed that two nonisomorphic graphs may possess identical distance-spectra. We already mentioned isospectral graphs when presenting the Hiickel matrix (see Section 2.19). A pair of the two polyhedral graphs on eight vertices that possess the same distance-spectra are shown in Figure 4.1. 

We will end with the outline of a new problem of experimental mathematics that arose in the process of writing this book and relates to isospectral graphs. 

We will introduce a few problems and a few solutions relating to experimental mathematics in the section following the story of isospectral graphs. 

FIGURE 3.1 The smallest pair of acyclic (eight vertices) and cyclic (six vertices) isospectral graphs. 

The next year, Mowshowitz reported the characteristic polynomials of all acyclic graphs having 10 and fewer vertices, from which, in addition to the pair of graphs having n = 8 vertices of Figure 3.1, one finds four pairs of isospectral graphs on... 

As was noticed, at that time, some isospectral graphs g and h generate isospectral pairs G, H via the ring enlargement procedure, and some do not. Why The answer is not known, so we have an open problem ... 

Under what conditions will a pair of isospectral graphs g, h upon enlargement produce isospectral pairs G and H ... 

K. Balasubramanian and S. C. Basak, Characterization of isospectral graphs using graph invariants and derived orthogonal parameters, J. Chem. Inf. Comput. Sci. 38 (1998) 367-373. 

---