WorksMathematics
Domination in token graphs of graphs with domination number two
Abstract
The -token graph of a graph is the graph whose vertices are the -subsets of , with two -subsets adjacent if and only if their symmetric difference is an edge of . In this paper we study the domination number of for graphs whose domination number is at least two, with a primary focus on the case . For , we give an upper bound for in terms of a dominating pair of , and show that this bound is sharp for every double star with ; moreover, we determine the exact value for every double star, namely for . We also prove that for every graph on vertices with , with equality for the graphs with the maximum number of edges among those with . Then, we focus on complete bipartite graphs; we give upper bounds for that match the exact values independently established in recent work, together with a short proof that . For we show that equals, up to lower-order terms, the Turán number , and we determine exactly, obtaining ; for , determining the leading constant is related to the still-open Turán conjecture for 3-uniform hypergraphs. Finally, for even, we prove that .