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/