
arXiv: 2010.04539
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
symmetric power of graph, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 05C69, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), double vertex graph, QA1-939, token graph, FOS: Mathematics, Mathematics - Combinatorics, well-covered graph, Combinatorics (math.CO), independence number, Mathematics
symmetric power of graph, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 05C69, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), double vertex graph, QA1-939, token graph, FOS: Mathematics, Mathematics - Combinatorics, well-covered graph, Combinatorics (math.CO), independence number, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
