Repositori Obert UdL
Publicación
Artículo científico (JournalArticle)
On the Laplacian spectra of token graphs
We study the Laplacian spectrum of token graphs, also called
symmetric powers of graphs. The k-token graph Fk(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 Fh(G) is contained in the Laplacian
spectrum of Fk(G). We also show that the doubled odd
graphs and doubled Johnson graphs can be obtained as token
graphs of the complete graph Kn and the star Sn = K1,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 wellknown 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., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
Proyecto:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PGC2018-095471-B-I00
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 MTM2017-83271-R
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2019-104129GB-I00
,
EC / H2020 734922