Let V₁, V₂ be a partition of the vertex set in a graph G, and let denote the least number of vertices needed in G to dominate . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| 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 γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1169,
author = {Zsolt Tuza and Preben Dahl Vestergaard},
title = {Domination in partitioned graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {22},
year = {2002},
pages = {199-210},
zbl = {1016.05057},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1169}
}
Zsolt Tuza; Preben Dahl Vestergaard. Domination in partitioned graphs. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 199-210. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1169/
[000] [1] B.L. Hartnell and P.D. Vestergaard, Partitions and dominations in a graph, Manuscript, pp. 1-10.
[001] [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., New York, N.Y., 1998). | Zbl 0890.05002
[002] [3] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104. | Zbl 0489.05049
[003] [4] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (3) (1996) 277-295, doi: 10.1017/S0963548300002042. | Zbl 0857.05052
[004] [5] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congressus Numerantium 132 (1998) 85-91. | Zbl 0951.05079