On the Laplacian spectra of token graphs
On the Laplacian spectra of token graphs
复制标题
关于标记图的拉普拉斯谱
DOI：
10.1016/j.laa.2021.05.005
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
F. Martínez
中科院分区：
文献类型：
--
作者：
C. Dalfó;F. Duque;R. Fabila;M. Fiol;C. Huemer;A. Trujillo;F. Martínez
本文研究了符号图的Laplacian谱，也称为图的对称幂。图G的k-令牌图Fk（G）是指其顶点是G中顶点的k-子集，且其中两个顶点的对称差是G中一对相邻顶点时，它们相邻的图。本文给出了给定图的任意两个标记图的Laplacian谱之间的关系。特别地，我们证明了对任意整数h和k，使得1≤ h≤ k≤ n2，Fh（G）的Laplacian谱包含在Fk（G）的Laplacian谱中.我们还证明了双奇图和双约翰逊图可以分别作为完全图Kn和星星Sn = K1，n-1的标记图.此外，我们还得到了图G的k-记号图与其补图G的k-记号图的谱之间的关系。这推广到令牌图一个众所周知的性质，即G的拉普拉斯特征值与G的拉普拉斯特征值密切相关。最后，双奇图和双约翰逊图提供了两个无限族，在这两个无限族中，原图和它的记号图的代数连通性是一致的.此外，我们猜想，这是任何图G和它的令牌图的情况。
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph F k (G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1≤ h≤ k≤ n 2, the Laplacian spectrum of F h (G) is contained in the Laplacian spectrum of F k (G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph K n and the star S n= K 1, n− 1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G‾. This generalizes to tokens graphs a well-known property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G‾. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph.