Domination Subdivision Numbers

Teresa W. Haynes; Sandra M. Hedetniemi; Stephen T. Hedetniemi; David P. Jacobs; James Knisely; Lucas C. van der Merwe

Discussiones Mathematicae Graph Theory (2001)

  • Volume: 21, Issue: 2, page 239-253
  • ISSN: 2083-5892

Abstract

top
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number s d γ ( G ) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that 1 ≤ s d γ ( G ) ≤ 3 for any graph G. We give a counterexample to this conjecture. On the other hand, we show that s d γ ( G ) ≤ γ ( G ) + 1 for any graph G without isolated vertices, and give constant upper bounds on s d γ ( G ) for several families of graphs.

How to cite

top

Teresa W. Haynes, et al. "Domination Subdivision Numbers." Discussiones Mathematicae Graph Theory 21.2 (2001): 239-253. <http://eudml.org/doc/270326>.

@article{TeresaW2001,
abstract = {A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $sd_γ(G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 ≤ sd_γ(G) ≤ 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that $sd_γ(G) ≤ γ(G)+1$ for any graph G without isolated vertices, and give constant upper bounds on $sd_γ(G)$ for several families of graphs.},
author = {Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; subdivision},
language = {eng},
number = {2},
pages = {239-253},
title = {Domination Subdivision Numbers},
url = {http://eudml.org/doc/270326},
volume = {21},
year = {2001},
}

TY - JOUR
AU - Teresa W. Haynes
AU - Sandra M. Hedetniemi
AU - Stephen T. Hedetniemi
AU - David P. Jacobs
AU - James Knisely
AU - Lucas C. van der Merwe
TI - Domination Subdivision Numbers
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 2
SP - 239
EP - 253
AB - A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $sd_γ(G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 ≤ sd_γ(G) ≤ 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that $sd_γ(G) ≤ γ(G)+1$ for any graph G without isolated vertices, and give constant upper bounds on $sd_γ(G)$ for several families of graphs.
LA - eng
KW - domination; subdivision
UR - http://eudml.org/doc/270326
ER -

References

top
  1. [1] Arumugam, private communication, June 2000. 
  2. [2] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079. Zbl0602.05043
  3. [3] D. Hare and W. McCuaig, A characterization of graphs whose domination and matching numbers are equal, unpublished manuscript, 1998. 
  4. [4] T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000) 271-280, doi: 10.7151/dmgt.1126. Zbl0984.05066
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs (Advanced Topics, Marcel Dekker, Inc., New York, 1998). Zbl0883.00011
  7. [7] T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivision numbers, submitted. Zbl1020.05048
  8. [8] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104. Zbl0489.05049
  9. [9] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and matching number, Utilitas Math. 55 (1999) 65-72. Zbl0940.05058

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.