On the connectivity of token graphs of trees
R Fabila-Monroy, J Leaños… - Discrete Mathematics …, 2022 - dmtcs.episciences.org
Discrete Mathematics & Theoretical Computer Science, 2022•dmtcs.episciences.org
Let k and n be integers such that 1≦k≦n-1, and let G be a simple graph of order n. The k-
token graph F_k(G) of G is the graph whose vertices are the k-subsets of V(G), where two
vertices are adjacent in F_k(G) whenever their symmetric difference is an edge of G. In this
paper we show that if G is a tree, then the connectivity of F_k(G) is equal to the minimum
degree of F_k(G).
token graph F_k(G) of G is the graph whose vertices are the k-subsets of V(G), where two
vertices are adjacent in F_k(G) whenever their symmetric difference is an edge of G. In this
paper we show that if G is a tree, then the connectivity of F_k(G) is equal to the minimum
degree of F_k(G).
Let and be integers such that , and let be a simple graph of order . The -token graph of is the graph whose vertices are the -subsets of , where two vertices are adjacent in whenever their symmetric difference is an edge of . In this paper we show that if is a tree, then the connectivity of is equal to the minimum degree of .
dmtcs.episciences.org