# Domination in partitioned graphs

Zsolt Tuza; Preben Dahl Vestergaard

Discussiones Mathematicae Graph Theory (2002)

- Volume: 22, Issue: 1, page 199-210
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topZsolt Tuza, and Preben Dahl Vestergaard. "Domination in partitioned graphs." Discussiones Mathematicae Graph Theory 22.1 (2002): 199-210. <http://eudml.org/doc/270682>.

@article{ZsoltTuza2002,

abstract = {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δ)/(δ).},

author = {Zsolt Tuza, Preben Dahl Vestergaard},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; dominating set; domination number; vertex partition},

language = {eng},

number = {1},

pages = {199-210},

title = {Domination in partitioned graphs},

url = {http://eudml.org/doc/270682},

volume = {22},

year = {2002},

}

TY - JOUR

AU - Zsolt Tuza

AU - Preben Dahl Vestergaard

TI - Domination in partitioned graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2002

VL - 22

IS - 1

SP - 199

EP - 210

AB - 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δ)/(δ).

LA - eng

KW - graph; dominating set; domination number; vertex partition

UR - http://eudml.org/doc/270682

ER -

## References

top- [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). Zbl0890.05002
- [3] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104. Zbl0489.05049
- [4] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (3) (1996) 277-295, doi: 10.1017/S0963548300002042. Zbl0857.05052
- [5] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congressus Numerantium 132 (1998) 85-91. Zbl0951.05079