Abstract
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of \(V(G) \setminus S\) is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. 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. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that \({\rm sd}_{\gamma} (G) \le \delta(G) + 1\) for any graph G with \(\delta(G) \ge 2\). In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bhattacharya, A., Vijayakumar, G.R.: Effect of edge-subdivision on vertex-domination in a graph. Discuss. Math. Graph Theory 22, 335–347 (2002)
Favaron, O., Haynes, T.W., Hedetniemi, S.T.: Domination subdivision numbers in graphs. Utilitas Math. 66, 195–209 (2004)
Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Jacobs, D.P., Knisely, J., van der Merwe, L.C.: Domination subdivision numbers. Discuss. Math. Graph Theory 21, 239–253 (2001)
Haynes, T.W., Henning, M.A., Hopkins, L.S.: Total domination subdivision numbers of graphs. Discuss. Math. Graph Theory 24, 457–467 (2004).
Velammal, S.: Studies in Graph Theory: Covering, Independence, Domination and Related Topics. Ph.D. Thesis, Manonmaniam Sundaranar University, Tirunelveli (1997)
West, D.B.: Introduction to Graph Theory. Prentice-Hall, Inc (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Favaron, O., Karami, H. & Sheikholeslami, S.M. Disproof of a Conjecture on the Subdivision Domination Number of a Graph. Graphs and Combinatorics 24, 309–312 (2008). https://doi.org/10.1007/s00373-008-0788-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-008-0788-6