Clique-inserted-graphs and spectral dynamics of clique-inserting. (English) Zbl 1148.05048

Summary: Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph \(G\) of degree \(r>0\), the graph obtained by replacing every vertex of \(G\) with a complete graph of order \(r\) is called the clique-inserted-graph of \(G\), denoted as \(C(G)\). We obtain a formula for the characteristic polynomial of \(C(G)\) in terms of the characteristic polynomial of \(G\). Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph \(G\). For any \(r\)-regular graph \(G\) with \(r>2\), let \(S(G)\) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of \(G\). We discover that the set of limit points of \(S(G)\) is a fractal with the maximum \(r\) and the minimum - 2, and that the fractal is independent of the structure of the concerned regular graph \(G\) as long as the degree \(r\) of \(G\) is fixed. It follows that for any integer \(r>2\) there exist infinitely many connected \(r\)-regular graphs (or, non-regular graphs with \(r\) as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any \(k\)th iterated clique-inserted-graph and other related results.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI


[1] Biggs, N., Algebraic graph theory, (1974), Cambridge Univ. Press Cambridge · Zbl 0284.05101
[2] Brown, J.I.; Hickman, C.A., On chromatic roots of large subdivisions of graphs, Discrete math., 242, 1-3, 17-30, (2002) · Zbl 0995.05059
[3] F.C. Bussemaker, S. Cobbeljec, D.M. Cvetković, I.J. Seidel, Computer investigation of cubic graphs, Technishe Hogeschool Eindhoven, Report 76-WSK-01, 1976
[4] Cao, D.-S.; Hong, Y., Graph characterized by the second eigenvalue, J. graph theory, 17, 3, 325-331, (1993) · Zbl 0786.05055
[5] Cao, D.-S.; Hong, Y., The distribution of eigenvalues of graphs, Linear algebra appl., 216, 211-224, (1995) · Zbl 0820.05047
[6] Chang, S.-C.; Shrock, R., Zeros of the Jones polynomial for families of knots and links, Phys. A, 301, 196-218, (2001) · Zbl 0979.57004
[7] Y.-C. Chen, Family of invariant Cantor sets as orbits of differential equations, 2006, preprint
[8] Chung, F.R.K., Spectral graph theory, Amer. math. soc., (1997), Providence, RI · Zbl 0872.05052
[9] Cvetković, D.M.; Doob, M.; Gutman, I.; Torgasev, A., Recent results in the theory of graph spectra, (1988), North-Holland Amsterdam · Zbl 0634.05054
[10] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs, (1980), Academic Press New York · Zbl 0458.05042
[11] Cvetković, D.M.; Rowlinson, P.; Simić, S., Eigenspaces of graphs, (1997), Cambridge Univ. Press Cambridge · Zbl 0878.05057
[12] Devaney, R.L., An introduction to chaotic dynamical systems, (1989), Addison-Wesley New York · Zbl 0695.58002
[13] Deza, M.; Grishukhin, V.; Shtogrin, M., Scale-isometric polytopal graphs in hypercubes and cubic lattices, polytopes in hypercubes and \(\mathbb{Z}_n\), (2004), Imperial College Press · Zbl 1054.52007
[14] Doob, M., The limit point of eigenvalues of graphs, Linear algebra appl., 114/115, 659-662, (1989) · Zbl 0671.05050
[15] Falconer, K., Fractal geometry: mathematical foundations and applications, (1990), John Wiley & Sons West Sussex · Zbl 0689.28003
[16] Godsil, C.D., Algebraic combinatorics, (1993), Chapman & Hall New York · Zbl 0814.05075
[17] Godsil, C.D.; McKay, B.D., Constructing cospectral graphs, Aequationes math., 25, 257-268, (1982) · Zbl 0527.05051
[18] Godsil, C.D.; Royle, G., Algebraic graph theory, (2001), Springer New York · Zbl 1026.05046
[19] Hoffman, A.J., On limit points of spectral radii of non-negative symmetric integer matrices, (), 165-172
[20] Hoffman, A.J., On limit points of the least eigenvalue of a graph, Ars combin., 3, 3-14, (1977) · Zbl 0445.05067
[21] Jin, X.; Zhang, F., Zeros of the Jones polynomial for families of knots and links, Phys. A, 328, 391-402, (2003)
[22] Jin, X.; Zhang, F., Jones polynomials and their zeros for a family of links, Phys. A, 333, 183-196, (2004)
[23] Lovász, L., Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001
[24] Lovász, L.; Plummer, M.D., Matching theory, Ann. discrete math., vol. 29, (1986), North-Holland Amsterdam · Zbl 0618.05001
[25] Mader, W., Minimale n-fach kantenzusammenhangende graphen, Math. ann., 191, 21-28, (1971) · Zbl 0198.29202
[26] Medio, A.; Raines, B.E., Inverse limit spaces arising from problems in economics, Topology appl., 153, 3437-3449, (2006) · Zbl 1105.37055
[27] Palis, J.; Takens, F., Hyperbolicity and sensitive chaotic dynamics at homoclinic bifurcations: fractal dimensions and infinitely many attractors, (1993), Cambridge University Press Cambridge · Zbl 0790.58014
[28] Robinson, C., Dynamical systems—stability, symbolic dynamics, and chaos, (1995), CRC Press London · Zbl 0853.58001
[29] Schwenk, A.J., Almost all trees are cospectral, (), 275-307 · Zbl 0261.05102
[30] Schwenk, A.J., Computing the characteristic polynomial of a graph, (), 153-172
[31] Shearer, J.B., On the distribution of the maximum eigenvalue of graphs, Linear algebra appl., 113/114, 17-20, (1989) · Zbl 0672.05059
[32] Shrock, R.; Tsai, S.-H., Asymptotic limits and zeros of chromatic polynomials and ground-state entropy of Potts antiferromagnets, Phys. rev. E, 55, 5165-5178, (1997)
[33] Wu, F.W.; Wang, J., Zeros of the Jones polynomial, Phys. A, 296, 483-494, (2001) · Zbl 0969.12500
[34] Zhang, F.; Chen, Z., Limit points of eigenvalues of (di)graphs, Czechoslovak math. J., 56(131), 3, 895-902, (2006) · Zbl 1164.05412
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.