Domination in partitioned graphs

Zsolt Tuza; Preben Dahl Vestergaard

Discussiones Mathematicae Graph Theory (2002)

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

Abstract

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

How to cite

top

Zsolt 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. [1] B.L. Hartnell and P.D. Vestergaard, Partitions and dominations in a graph, Manuscript, pp. 1-10. 
  2. [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. [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. [4] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (3) (1996) 277-295, doi: 10.1017/S0963548300002042. Zbl0857.05052
  5. [5] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congressus Numerantium 132 (1998) 85-91. Zbl0951.05079

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.