paper

Well-covered Token Graphs

arXiv:2010.04539

Abstract

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.

21 pages