DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

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

DOMINATION IN PARTITIONED GRAPHS

 Zsolt Tuza 

Computer and Automation Institute
Hungarian Academy of Sciences, Budapest
and
Department of Computer Science
University of Veszprém, Hungary
e-mail: tuza@sztaki.hu

Preben Dahl Vestergaard

Department of Mathematics, Aalborg University
Fredrik Bajers Vej 7E, DK-9220
Aalborg Ø, Denmark
e-mail: pdv@math.auc.dk

Abstract

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

References

[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