论文标题
在令牌图的拉普拉斯谱上
On the Laplacian spectra of token graphs
论文作者
论文摘要
我们研究了令牌图的拉普拉斯谱，也称为图形的对称力量。图$ g $的$ k $ token Graph $ f_k（g）$是其顶点是$ g $的$ k $ - subset，其中两个是在$ g $中的两对相邻顶点时，其中两个是相邻的。在本文中，我们给出了给定图的任何两个令牌图的拉普拉斯光谱之间的关系。特别是，我们表明，对于任何整数$ h $和$ k $，使得$ 1 \ le h \ le k \ le \ le \ frac {n} {2} $，$ f_h（g）$的laplacian Spectrum septrum包含在laplacian Spectrum的$ f_k（g）$中。我们还表明，可以分别作为完整图$ k_n $和star $ s_ {n} = k_ {1，n-1，n-1} $获得双奇数图和加倍的约翰逊图。此外，我们获得了$ g $的$ k $ token图的光谱与其补充$ \ overline {g} $的$ k $ token图之间的关系。这将图形的拉普拉斯特征值概述为令牌图。最后，双奇数图和加倍的约翰逊图提供了两个无限的家族，以及其他一些家族，其中原始图的代数连接及其令牌图一致。此外，我们猜测对于任何图形$ 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\le h\le k\le \frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double 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 $\overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double 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.
