Clique-inserted-graphs and spectral dynamics of clique-inserting
Clique-inserted-graphs and spectral dynamics of clique-inserting
复制标题
DOI：
10.1016/j.jmaa.2008.08.036
复制
发表时间：
2009
影响因子：
1.3
通讯作者：
Fuji Zhang;Yi-Chiuan Chen;Zhibo Chen
中科院分区：
文献类型：
--
作者：
Fuji Zhang;Yi-Chiuan Chen;Zhibo Chen
受研究截顶多面体谱的启发，我们考虑截顶插入图。对于r>0度的正则图G，用r阶完全图替换G的每个顶点所得到的图称为G的插入图，记为C（G）。利用G的特征多项式得到了C（G）的特征多项式的一个公式。此外，我们还分析了正则图G上的子图插入迭代的谱动力学。对任意r-正则图G，设S（G）表示G的所有迭代插入图的特征值集之并，其中r>2.我们发现S（G）的极限点集是一个最大为r、最小为−2的分形，并且只要G的度r一定，该分形与G的结构无关.由此可知，对于任意整数r>2，存在无穷多个连通r-正则图（或r为最大度的非正则图），它们在分形中任意给定点周围的任意小区间内具有任意多个不同的特征值。给出了任意第k次迭代的连通插入图的生成树个数的计算公式及相关结果。
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.