Geodesic
Domination Subdivision Numbers
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 239-253.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: domination, subdivision 
@article{DMGT_2001_21_2_a8,
     author = {Haynes, Teresa and Hedetniemi, Sandra and Hedetniemi, Stephen and Jacobs, David and Knisely, James and van der Merwe, Lucas},
     title = {Domination {Subdivision} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {239--253},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a8/}
}
TY  - JOUR
AU  - Haynes, Teresa
AU  - Hedetniemi, Sandra
AU  - Hedetniemi, Stephen
AU  - Jacobs, David
AU  - Knisely, James
AU  - van der Merwe, Lucas
TI  - Domination Subdivision Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 239
EP  - 253
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a8/
LA  - en
ID  - DMGT_2001_21_2_a8
ER  - 
%0 Journal Article
%A Haynes, Teresa
%A Hedetniemi, Sandra
%A Hedetniemi, Stephen
%A Jacobs, David
%A Knisely, James
%A van der Merwe, Lucas
%T Domination Subdivision Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 239-253
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a8/
%G en
%F DMGT_2001_21_2_a8
Haynes, Teresa; Hedetniemi, Sandra; Hedetniemi, Stephen; Jacobs, David; Knisely, James; van der Merwe, Lucas. Domination Subdivision Numbers. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 239-253. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a8/

[1] Arumugam, private communication, June 2000.

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

[3] D. Hare and W. McCuaig, A characterization of graphs whose domination and matching numbers are equal, unpublished manuscript, 1998.

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

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs (Advanced Topics, Marcel Dekker, Inc., New York, 1998).

[7] T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivision numbers, submitted.

[8] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104.

[9] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and matching number, Utilitas Math. 55 (1999) 65-72.