Show simple item record

dc.contributor.authorDalfó, Cristina
dc.contributor.authorDuque, F.
dc.contributor.authorFabila Monroy, R.
dc.contributor.authorFiol, Miguel Angel
dc.contributor.authorHuemer, Clemens
dc.contributor.authorZaragoza Martínez, F.J.
dc.contributor.authorTrujillo Negrete, A.L.
dc.description.abstractWe 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.ca_ES
dc.description.sponsorshipThis 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 734922ca_ES
dc.relation.isformatofReproducció del document publicat a
dc.relation.ispartofLinear Algebra and its Applications, 2021, vol. 625, p. 322-348ca_ES
dc.rightscc-by-nc-nd (c) Dalfó et al., 2021ca_ES
dc.subjectToken graphca_ES
dc.subjectLaplacian spectrumca_ES
dc.subjectAlgebraic connectivityca_ES
dc.subjectBinomial matrixca_ES
dc.subjectAdjacency spectrumca_ES
dc.titleOn the Laplacian spectra of token graphsca_ES

Files in this item


This item appears in the following Collection(s)

Show simple item record

cc-by-nc-nd (c) Dalfó et al., 2021
Except where otherwise noted, this item's license is described as cc-by-nc-nd (c) Dalfó et al., 2021