On the Laplacian spectra of token graphs
View/Open
Issue date
2021Author
Duque, F.
Fabila Monroy, R.
Fiol, Miguel Angel
Huemer, Clemens
Zaragoza Martínez, F.J.
Trujillo Negrete, A.L.
Suggested citation
Dalfó, Cristina;
Duque, F.;
Fabila Monroy, R.;
Fiol, Miguel Angel;
Huemer, Clemens;
Zaragoza Martínez, F.J.;
Trujillo Negrete, A.L.;
.
(2021)
.
On the Laplacian spectra of token graphs.
Linear Algebra and its Applications, 2021, vol. 625, p. 322348.
https://doi.org/10.1016/j.laa.2021.05.005.
Metadata
Show full item recordAbstract
We study the Laplacian spectrum of token graphs, also called
symmetric powers of graphs. The ktoken graph Fk(G) of
a graph G is the graph whose vertices are the ksubsets 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 ktoken graph of G and the ktoken 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.
Is part of
Linear Algebra and its Applications, 2021, vol. 625, p. 322348European research projects
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as ccbyncnd (c) Dalfó et al., 2021
Related items
Showing items related by title, author, creator and subject.

A general method to obtain the spectrum and local spectra of a graph from its regular partitions
Dalfó, Cristina; Fiol, Miguel Angel (International Linear Algebra Society, 20200712)It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also ... 
The spectra of lifted digraphs
Dalfó, Cristina; Fiol, Miguel Angel; Sirán, Jozef (Springer, 20190102)We present a method to derive the complete spectrum of the lift Γα of a base digraph Γ , with voltage assignment α on a (finite) group G. The method is based on assigning to Γ a quotientlike matrix whose entries are ... 
An algebraic approach to lifts of digraphs
Dalfó, Cristina; Fiol, Miguel Angel; Miller, Mirka; Ryan, Joe; Sirán, Josef (Elsevier, 2018)We present some applications of a new matrix approach for studying the properties of the lift of a voltage digraph, which has arcs weighted by the elements of a group. As a main result, when the involved group is Abelian, ...