On the Laplacian spectra of token graphs

DOI10.1016/J.LAA.2021.05.005zbMATH Open1465.05098arXiv2012.00808OpenAlexW3161163465MaRDI QIDQ2032264FDOQ2032264

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)

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.

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

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

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)

Cites Work

• Eigenvalues of the Laplacian of a graph^∗
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distance biregular bipartite graphs
• A note on the ranks of set-inclusion matrices
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• Symmetric squares of graphs
• Token graphs
• On Middle Cube Graphs
• Title not available (Why is that?)
• Survey of double vertex graphs
• Title not available (Why is that?)
• Regularity and planarity of token graphs
• Non-isomorphic graphs with cospectral symmetric powers
• A general method to obtain the spectrum and local spectra of a graph from its regular partitions
• Double vertex graphs and complete double vertex graphs

Cited In (11)

• On the spectra of token graphs of cycles and other graphs
• On the spectra and spectral radii of token graphs
• On the algebraic connectivity of some token graphs
• Garland's method for token graphs
• Token graphs of Cayley graphs as lifts
• Automorphism group of 2-token graph of the Hamming graph
• Edge-transitive token graphs
• A general method to find the spectrum and eigenspaces of the \(k\)-token graph of a cycle, and 2-token through continuous fractions
• The automorphisms of 2-token graphs
• Spectral properties of token graphs
• On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of 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)