With F. M. Abdelmalek, Esther Vander Meulen, and Adam Van Tuyl. In Discussiones Mathematicae Graph Theory 33, no. 1 (Warsaw: Sciendo Publishing, 2021)

The k-token graph Tk(G) is the graph whose vertices are the k-subsets ofvertices of a graph G, with two vertices of Tk(G) adjacent if their symmetricdifference 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 anarbitrary graph G, we show that if T2(G) is well-covered, then the girth ofGis at most four. We include upper and lower bounds on the independencenumber of Tk(G), and provide some families of well-covered token graphs.

Publication Information


Dr. Kevin Vander Meulen

Publisher or Title:


Publication date: