Independence and matching number for some token graphs

Abstract

Let G be a graph of order n and let k ∈ {1, . . . , n−1}. The k-token graph Fk(G) of G is the graph whose vertices are the k-subsets of V (G), where two vertices are adjacent in Fk(G) whenever their symmetric difference is an edge of G. We study the independence and matching numbers of Fk(G). We present a tight lower bound for the matching number of Fk(G) for the case in which G has either a perfect matching or an almost perfect matching. Also, we estimate the independence number for bipartite ktoken graphs, and determine the exact value for some graphs.