On the algebraic connectivity of some token 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 are adjacent whenever their symmetric difference is a pair of adjacent vertices in G . It was proved that the algebraic connectivity of F k ( G ) equals the algebraic connectivi...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algebraic combinatorics 2024, Vol.60 (1), p.45-56
Main Authors: Dalfó, C., Fiol, M. A.
Format: Article
Language:English
Subjects:
Apexes
Combinatorial analysis
Combinatorics
Computer Science
Convex and Discrete Geometry
Graph theory
Graphs
Group Theory and Generalizations
Lattices
Mathematics
Mathematics and Statistics
Order
Ordered Algebraic Structures
Random walk
Trees (mathematics)
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 are adjacent whenever their symmetric difference is a pair of adjacent vertices in G . It was proved that the algebraic connectivity of F k ( G ) equals the algebraic connectivity of G with a proof using random walks and interchange of processes on a weighted graph. However, no algebraic or combinatorial proof is known, and it would be a hit in the area. In this paper, we algebraically prove that the algebraic connectivity of F k ( G ) equals the one of G for new infinite families of graphs, such as trees, some graphs with hanging trees, and graphs with minimum degree large enough. Some examples of these families are the following: the cocktail party graph, the complement graph of a cycle, and the complete multipartite graph.
ISSN:0925-9899
1572-9192
DOI:10.1007/s10801-024-01323-0