Clique-inserted-graphs and spectral dynamics of clique-inserting

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.