With F. M. Abdelmalek, Esther Vander Meulen, and Adam Van Tuyl. In Discussiones Mathematicae Graph Theory 43 (2023) 767-792.

The k-token graph Tk(G) is the graph whose vertices are the k-subsets of vertices of a graph G, with two vertices of Tk(G) adjacent if their symmetric difference is an edge of G. We explore when Tk(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 Tk(G) is well-covered. For an arbitrary graph G, we show that if T2(G) is well-covered, then the girth of G is at most four. We include upper and lower bounds on the independence number of Tk(G), and provide some families of well-covered token graphs.

Publication Information


Dr. Kevin Vander Meulen

Publisher or Title:

Discussiones Mathematicae Graph Theory

Publication date: