ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 22(1) (2002) 199-210
DOI: 10.7151/dmgt.1169


 Zsolt Tuza 

Computer and Automation Institute
Hungarian Academy of Sciences, Budapest
Department of Computer Science
University of Veszprém, Hungary

Preben Dahl Vestergaard

Department of Mathematics, Aalborg University
Fredrik Bajers Vej 7E, DK-9220
Aalborg Ø, Denmark


Let V1, V2 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 Vi. We prove that γ12 ≤ [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 γ12 for graphs with minimum valency δ, and conjecture that γ12 ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ12) /|V(G)| is shown to grow with the order of [(logδ)/(δ)].

Keywords: graph, dominating set, domination number, vertex partition.

2000 Mathematics Subject Classification: 05C35, 05C70 (primary), 05C75 (secondary).


[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.

Received 10 November 2000
Revised 9 May 2001