- Tytuł:
- Well-covered token graphs
- Autorzy:
-
Abdelmalek, F.M.
Vander Meulen, Esther
Vander Meulen, Kevin N.
Van Tuyl, Adam - Tematy:
-
independence number
well-covered graph
token graph
double vertex graph
symmetric power of a graph - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/59898549.pdf Link otwiera się w nowym oknie
- Opis:
- 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł