On the Laplacian spectra of token graphs

DOI10.1016/J.LAA.2021.05.005MaRDI QIDQ2032264zbMATH OpenOpenAlexFDO

Authors C. Dalfó, R. Fabila-Monroy, Clemens Huemer, Ana Laura Trujillo-Negrete, F. J. Zaragoza Martínez, Frank Duque, Miquel Angel Fiol

Publication date 11 June 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2012.00808

zbMATH Keywords

Laplacian spectrumadjacency spectrumalgebraic connectivitycomplement graphdoubled odd graphbinomial matrixdoubled Johnson graphtoken graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $1lehleklefracn2$, 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 $overlineG$. 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.

Recommendations

• On the spectra of token graphs of cycles and other graphs
• The Laplacian spectra of graphs with a tree structure
• scientific article; zbMATH DE number 867649
• On the Laplacian spectrum of (\(\alpha,\omega\))-graphs
• Laplacian spectra and invariants of graphs
• scientific article; zbMATH DE number 2192118
• On the Laplacian spectral ratio of connected graphs
• Laplacian spectra and spanning trees of threshold graphs
• On the spectral characterizations of graphs
• On the Laplacian spectral radius of a graph

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 146670 (Why is no real title available?)
• scientific article; zbMATH DE number 863500 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• A general method to obtain the spectrum and local spectra of a graph from its regular partitions
• A note on the ranks of set-inclusion matrices
• Distance biregular bipartite graphs
• Double vertex graphs and complete double vertex graphs
• Eigenvalues of the Laplacian of a graph^∗
• Non-isomorphic graphs with cospectral symmetric powers
• On middle cube graphs
• Regularity and planarity of token graphs
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• Survey of double vertex graphs
• Symmetric squares of graphs
• Token graphs

Cited in

(19)

• On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs
• Automorphism groups of 2-token graph of Cartesian product of two cycles
• On the spectra of token graphs of cycles and other graphs
• On the spectra and spectral radii of token graphs
• Some bounds on the Laplacian eigenvalues of token graphs
• On the algebraic connectivity of some token graphs
• Garland's method for token graphs
• Automorphism groups of a class of 2-token graphs
• Laplacian spectral radius and integrality of token graphs
• Token graphs of Cayley graphs as lifts
• Automorphism group of 2-token graph of the Hamming graph
• Edge-transitive token graphs
• On the treewidth of token and Johnson graphs
• A general method to find the spectrum and eigenspaces of the k-token graph of a cycle, and 2-token through continuous fractions
• On some metric properties of supertoken graphs
• On token signed graphs
• The automorphisms of 2-token graphs
• On the algebraic connectivity of token graphs and graphs under perturbations
• Spectral properties of token graphs

This page was built for publication: On the Laplacian spectra of token graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032264)