2014/05/14 by Felix Goldberg, Goldberg, Felix, Deepak Rajendraprasad +3
Mathematics · #05B05 #05C69 #51E10 #51E15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05B05 #msc:05C69 #msc:51E10 #msc:51E15
paper · pdf · doi:10.48550/arxiv.1405.3436
arxiv created 2014/05/14 · arxiv updated 2014/05/15
We commence the study of domination in the incidence graphs of combinatorial designs. Let D be a combinatorial design and denote by γ(D) the domination number of the incidence (Levy) graph of D. We obtain a number of results about the domination numbers of various kinds of designs. For instance, a finite projective plane of order n, which is a symmetric (n2+n+1,n+1,1)-design, has γ=2n. %We also show that for any symmetric (v,k,λ)-design it holds that γ≤ 2k. We study at depth the domination numbers of Steiner systems and in particular of Steiner triple systems. We show that a STS(v) has γ≥ (2)/(3)v-1 and also obtain a number of upper bounds. The tantalizing conjecture that all Steiner triple systems on v vertices have the same domination number is proposed and is verified up to v ≤ 15. The structure of minimal dominating sets is also investigated, both for its own sake and as a tool in deriving lower bounds on γ. Finally, a number of open questions are proposed.