# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

# Discussiones Mathematicae Graph Theory

## 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