On the Laplacian spectra of token graphs
| dc.contributor.author | Dalfó, Cristina | |
| dc.contributor.author | Duque, F. | |
| dc.contributor.author | Fabila Monroy, R. | |
| dc.contributor.author | Fiol Mora, Miguel Ángel | |
| dc.contributor.author | Huemer, Clemens | |
| dc.contributor.author | Zaragoza Martínez, F.J. | |
| dc.contributor.author | Trujillo Negrete, A.L. | |
| dc.date.accessioned | 2021-09-01T08:43:54Z | |
| dc.date.available | 2021-09-01T08:43:54Z | |
| dc.date.issued | 2021 | |
| dc.description.abstract | 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. | ca_ES |
| dc.description.sponsorship | 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 | ca_ES |
| dc.identifier.doi | https://doi.org/10.1016/j.laa.2021.05.005 | |
| dc.identifier.idgrec | 031280 | |
| dc.identifier.issn | 0024-3795 | |
| dc.identifier.uri | http://hdl.handle.net/10459.1/71777 | |
| dc.language.iso | eng | ca_ES |
| dc.publisher | Elsevier | ca_ES |
| dc.relation | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PGC2018-095471-B-I00/ES/ESTUDIO MATEMATICO DE LOS FALLOS EN CASCADA EN SISTEMAS COMPLEJOS MEDIANTE INVARIANTES Y CENTRALIDADES EN GRAFOS. APLICACIONES A REDES REALES/ | ca_ES |
| dc.relation | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016/MTM2017-83271-R/ES/CRIPTOGRAFIA Y CODIGOS PARA APLICACIONES SEGURAS Y FIABLES/ | ca_ES |
| dc.relation | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-104129GB-I00/ES/TEORIA Y APLICACIONES DE CONFIGURACIONES DE PUNTOS Y REDES/ | |
| dc.relation.isformatof | Reproducció del document publicat a https://doi.org/10.1016/j.laa.2021.05.005 | ca_ES |
| dc.relation.ispartof | Linear Algebra and its Applications, 2021, vol. 625, p. 322-348 | ca_ES |
| dc.relation.projectID | info:eu-repo/grantAgreement/EC/H2020/734922/EU/CONNECT | ca_ES |
| dc.rights | cc-by-nc-nd (c) Dalfó et al., 2021 | ca_ES |
| dc.rights.accessRights | info:eu-repo/semantics/openAccess | ca_ES |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
| dc.subject | Token graph | ca_ES |
| dc.subject | Laplacian spectrum | ca_ES |
| dc.subject | Algebraic connectivity | ca_ES |
| dc.subject | Binomial matrix | ca_ES |
| dc.subject | Adjacency spectrum | ca_ES |
| dc.title | On the Laplacian spectra of token graphs | ca_ES |
| dc.type | info:eu-repo/semantics/article | ca_ES |
| dc.type.version | info:eu-repo/semantics/publishedVersion | ca_ES |