Geodesic
Domination in partitioned graphs
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 199-210.

Voir la notice de l'article provenant de la source Library of Science

Let V₁, V₂ be a partition of the vertex set in a graph G, and let γ_i denote the least number of vertices needed in G to dominate V_i. 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δ)/(δ).
Keywords: graph, dominating set, domination number, vertex partition 
@article{DMGT_2002_22_1_a16,
     author = {Tuza, Zsolt and Vestergaard, Preben},
     title = {Domination in partitioned graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {199--210},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a16/}
}
TY  - JOUR
AU  - Tuza, Zsolt
AU  - Vestergaard, Preben
TI  - Domination in partitioned graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 199
EP  - 210
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a16/
LA  - en
ID  - DMGT_2002_22_1_a16
ER  - 
%0 Journal Article
%A Tuza, Zsolt
%A Vestergaard, Preben
%T Domination in partitioned graphs
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 199-210
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a16/
%G en
%F DMGT_2002_22_1_a16
Tuza, Zsolt; Vestergaard, Preben. Domination in partitioned graphs. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 199-210. http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a16/

[1] B.L. Hartnell and P.D. Vestergaard, Partitions and dominations in a graph, Manuscript, pp. 1-10.

[2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., New York, N.Y., 1998).

[3] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104.

[4] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (3) (1996) 277-295, doi: 10.1017/S0963548300002042.

[5] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congressus Numerantium 132 (1998) 85-91.