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, Tome 21 (2001), p. 239-253 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270326 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1147,
     author = {Teresa W. Haynes and Sandra M. Hedetniemi and Stephen T. Hedetniemi and David P. Jacobs and James Knisely and Lucas C. van der Merwe},
     title = {Domination Subdivision Numbers},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {239-253},
     zbl = {1006.05042},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1147}
}

Teresa W. Haynes; Sandra M. Hedetniemi; Stephen T. Hedetniemi; David P. Jacobs; James Knisely; Lucas C. van der Merwe. Domination Subdivision Numbers. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 239-253. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1147/

[000] [1] Arumugam, private communication, June 2000.

[001] [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. | Zbl 0602.05043

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

[003] [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. | Zbl 0984.05066

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

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

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

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

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