Clique-inserted-graphs and spectral dynamics of clique-inserting |
| |
Authors: | Fuji Zhang Yi-Chiuan Chen Zhibo Chen |
| |
Institution: | a Department of Mathematics, Xiamen University, Xiamen 361005, China b Institute of Mathematics, Academia Sinica, Taipei 11529, Taiwan c Department of Mathematics, Penn State University, 4000 University Drive, McKeesport, PA 15132, USA |
| |
Abstract: | 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 kth iterated clique-inserted-graph and other related results. |
| |
Keywords: | Clique-inserted-graph Clique-inserting characteristic polynomial Spectra (of graph) Logistic map Cantor set Fractal |
本文献已被 ScienceDirect 等数据库收录! |
|