Well-covered Token Graphs

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.

This page was built for publication: Well-covered Token Graphs