ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


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


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


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.


[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