Domination in partitioned graphs
Zs. Tuza, Preben Dahl Vestergaard · Discussiones Mathematicae Graph Theory · 2002
Let V 1 ; V 2 be a partition of the vertex set in a graph G, let denote the domination number of G and let i denote the least number of vertices needed in G to dominate V i . We prove that 1 + 2 4 5 jV (G)j for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on 1 + 2 for graphs with minimum valency , and conjecture that 1 + 2 4 +3 jV (G)j for 5. As gets large, however, the largest possible value of ( 1 + 2 )=jV (G)j is shown to grow with the order of log .