On the spectra and spectral radii of token graphs
Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by Fk(G), has as vertices the (n/k) k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, Fk(Kn) is the Johnson graph J(...
| Autores: | ; ; |
|---|---|
| Tipo de documento: | Artículo |
| Estado: | Published version |
| Fecha de publicación: | 2024 |
| País: | España |
| Institución: | Universitat de Lleida (UdL) |
| Repositorio: | Repositori Obert UdL |
| OAI Identifier: | oai:repositori.udl.cat:10459.1/464851 |
| Acceso en línea: | https://doi.org/10.1007/s40590-023-00583-3 https://hdl.handle.net/10459.1/464851 |
| Nivel de acceso: | Acceso abierto |
| Palabra clave: | Token graph Adjacency spectrum Local spectrum Laplacian spectrum Algebraic connectivity Binomial matrix Spectral radius Walk-regular graph |
| _version_ | 1878736552251621376 |
|---|---|
| author | Reyes, Mónica Andrea |
| author2 | Dalfó, Cristina Fiol Mora, Miguel Ángel |
| author2_role | author author |
| author_browse | Dalfó, Cristina Fiol Mora, Miguel Ángel Reyes, Mónica Andrea |
| author_facet | Reyes, Mónica Andrea Dalfó, Cristina Fiol Mora, Miguel Ángel |
| author_role | author |
| collection | Repositori Obert UdL |
| description | Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by Fk(G), has as vertices the (n/k) k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, Fk(Kn) is the Johnson graph J(n, k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of Fk(G) in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of Fk(G) is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous’ spectral gap conjecture (which is now a theorem) is proposed. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | ES_91048b8da7f4eebf31f4a750da678708 |
| institution | Universitat de Lleida (UdL) |
| instname_str | Universitat de Lleida (UdL) |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:repositori.udl.cat:10459.1/464851 |
| publishDate | 2024 |
| publishDateSort | 2024 |
| publisher | Springer |
| publisherStr | Springer |
| reponame_str | Repositori Obert UdL |
| spelling | On the spectra and spectral radii of token graphs Reyes, Mónica Andrea Dalfó, Cristina Fiol Mora, Miguel Ángel Token graph Adjacency spectrum Local spectrum Laplacian spectrum Algebraic connectivity Binomial matrix Spectral radius Walk-regular graph Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by Fk(G), has as vertices the (n/k) k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, Fk(Kn) is the Johnson graph J(n, k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of Fk(G) in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of Fk(G) is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous’ spectral gap conjecture (which is now a theorem) is proposed. The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under Project 2017SGR1087 and by MICINN from the Spanish Government under Project PGC2018-095471-B-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023. Springer https://doi.org/10.1007/s40590-023-00583-3 https://hdl.handle.net/10459.1/464851 |
| spellingShingle | On the spectra and spectral radii of token graphs Reyes, Mónica Andrea Token graph Adjacency spectrum Local spectrum Laplacian spectrum Algebraic connectivity Binomial matrix Spectral radius Walk-regular graph |
| status_str | publishedVersion |
| title | On the spectra and spectral radii of token graphs |
| title_full | On the spectra and spectral radii of token graphs |
| title_fullStr | On the spectra and spectral radii of token graphs |
| title_full_unstemmed | On the spectra and spectral radii of token graphs |
| title_short | On the spectra and spectral radii of token graphs |
| title_sort | On the spectra and spectral radii of token graphs |
| topic | Token graph Adjacency spectrum Local spectrum Laplacian spectrum Algebraic connectivity Binomial matrix Spectral radius Walk-regular graph |
| topic_facet | Token graph Adjacency spectrum Local spectrum Laplacian spectrum Algebraic connectivity Binomial matrix Spectral radius Walk-regular graph |
| url | https://doi.org/10.1007/s40590-023-00583-3 https://hdl.handle.net/10459.1/464851 |