Well-covered Token Graphs
| Autor: | F.M. Abdelmalek, Adam Van Tuyl, Kevin N. Vander Meulen, Esther Vander Meulen |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| DOI: | 10.48550/arxiv.2010.04539 |
| Popis: | 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. Comment: 21 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|