PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 239-253
DOI: https://doi.org/10.7151/dmgt.1147

DOMINATION SUBDIVISION NUMBERS

Teresa W. Haynes Department of Mathematics East Tennessee State University Johnson City, TN 37614 USA

Sandra M. Hedetniemi, Stephen T. Hedetniemi and David P. Jacobs Department of Computer Science Clemson University, Clemson, SC 29634 USA

James Knisely Department of Mathematics Bob Jones University, Greenville, SC 29614 USA

Lucas C. van der Merwe Division of Mathematics and Science Northeast State Technical Community College Blountville, TN 37617 USA

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.

Keywords: domination, subdivision.

2000 Mathematics Subject Classification: 05C69, 05C70.

References

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

Received 21 December 2000