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

NSFC [10671162]; NSC [95-2115-M-001-023]Motivated by studying the spectra of truncated polyhedra, we consider the clique- insertedgraphs. 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. (C) 2008 Elsevier Inc. All rights reserved