Well-covered token graphs
Fred M. Abdelmalek, Esther Vander Meulen, Kevin N. Vander Meulen, Adam Van Tuyl · Discussiones Mathematicae Graph Theory · 2021
The k-token graph T k (G) is the graph whose vertices are the k-subsets of vertices of a graph G, with two vertices of T k (G) adjacent if their symmetric difference is an edge of G.We explore when T k (G) is a well-covered graph, that is, when all of its maximal independent sets have the same cardinality.For bipartite graphs G, we classify when T k (G) is well-covered.For an arbitrary graph G, we show that if T 2 (G) is well-covered, then the girth of G is at most four.We include upper and lower bounds on the independence number of T k (G), and provide some families of well-covered token graphs.