betaFeedback

WorksMathematics

Domination in token graphs of graphs with domination number two

Abstract

The kk-token graph Fk(G)F_k(G) of a graph GG is the graph whose vertices are the kk-subsets of V(G)V(G), with two kk-subsets adjacent if and only if their symmetric difference is an edge of GG. In this paper we study the domination number of Fk(G)F_k(G) for graphs GG whose domination number γ(G)γ(G) is at least two, with a primary focus on the case γ(G)=2γ(G)=2. For k=2k=2, we give an upper bound for γ(F2(G))γ(F_2(G)) in terms of a dominating pair of GG, and show that this bound is sharp for every double star Sa,bS_{a,b} with 2≤a≤b2\le a\le b; moreover, we determine the exact value for every double star, namely γ(F2(Sa,b))=2a+b−1γ(F_2(S_{a,b}))=2a+b-1 for 1≤a≤b1\le a\le b. We also prove that γ(F2(G))≥⌈n/2⌉γ(F_2(G))\ge\lceil n/2\rceil for every graph GG on nn vertices with γ(G)≥2γ(G)\geq2, with equality for the graphs with the maximum number of edges among those with γ(G)≥2γ(G)\geq2. Then, we focus on complete bipartite graphs; we give upper bounds for γ(F2(Kr,t))γ(F_2(K_{r,t})) that match the exact values independently established in recent work, together with a short proof that γ(F2(K2,n−2))=n−2γ(F_2(K_{2,n-2}))=n-2. For k≥3k\ge3 we show that γ(Fk(K2,n−2))γ(F_k(K_{2,n-2})) equals, up to lower-order terms, the Turán number T(n−2,k,k−1)T(n-2,k,k-1), and we determine γ(F3(K2,n−2))γ(F_3(K_{2,n-2})) exactly, obtaining T(n−2,3,2)+n−4=n2/4+O(n)T(n-2,3,2) +n-4=n^2/4+O(n); for k=4k=4, determining the leading constant is related to the still-open Turán conjecture for 3-uniform hypergraphs. Finally, for n≥12n\geq 12 even, we prove that γ(F3(Kn/2,n/2))=748n2+O(n)γ\left(F_3(K_{n/2,n/2})\right) =\frac{7}{48}n^2+O(n).

Paper details

vlnc:W_47vmx2c3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude (Anthropic)

View statement
Looking for related papers…