The convex domination subdivision number of a graph

Document Type : Original paper

Authors

1 Gdańsk University of Technology

2 Azarbaijan Shahid Madani University

Abstract

Let $G=(V,E)$ be a simple graph. A set $D\subseteq V$ is a dominating set of $G$ if every vertex in $V\setminus D$ has at least one neighbor in $D$. The distance $d_G(u,v)$ between two vertices $u$ and $v$ is the length of a shortest $(u,v)$-path in $G$. An $(u,v)$-path of length $d_G(u,v)$ is called an $(u,v)$-geodesic. A set $X\subseteq V$ is convex in $G$ if vertices from all $(a, b)$-geodesics belong to $X$ for any two vertices $a,b\in X$. A set $X$ is a convex dominating set if it is convex and dominating set. The {\em convex domination number} $\gamma_{\rm con}(G)$ of a graph $G$ equals the minimum cardinality of a  convex dominating set in $G$. {\em The convex domination subdivision number} sd$_{\gamma_{\rm con}}(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 convex domination number. In this paper we initiate the study of convex domination subdivision number and we establish upper bounds for it. 

Keywords

Main Subjects

References

[1] H. Aram, S. M. Sheikholeslami, O. Favaron, Domination subdivision numbers of trees, Discrete Math. 309 ( 2009), 622–628.
[2] M. Atapour, S. M. Sheikholeslami, A. Khodkar, Roman domination subdivision number of graphs, Aequationes Math. 78 (2009), 237–245.
[3] M. Atapour, S. M. Sheikholeslami, A. Hansberg, L. Volkmann, A. Khodkar, 2-domination subdivision number of graphs, AKCE J. Graphs. Combin. 5 (2008), 165–173.
[4] J. Cyman, M. Lemańska, J. Raczek, Graphs with convex domination number close to their order, Discuss. Math. Graph Theory 26 (2006), 307-316.
[5] N. Dehgardi, S.M. Sheikholeslami, L. Volkmann, The rainbow domination subdivision numbers of graphs, Mat. Vesnik 67 (2015), 102-114.
[6] M. Dettlaff, M. Lemańska, S. Kosary, S. M. Sheikholeslami, Weakly convex domination subdivision number of a graph, Filomat (To appear)
[7] M. Dettlaff, M. Lemańska, Influence of edge subdivision on the convex domination number, Australas. J. Combin. 53 (2012), 19–30.
[8] M. Falahat, S.M. Sheikholeslami, L. Volkmann, New bounds on the rainbow domination subdivision number, Filomat 28 (2014), 615-622.
[9] O. Fvaron, H. Karami, S.M. Sheikholeslami, Disprove of a conjecture the domination subdivision number of a graph, Graphs Combin. 24 (2008), 309-312.
[10] O. Favaron, H. Karami, S. M. Sheikholeslami, Connected domination  subdivision numbers of graphs, Util. Math. 77 (2008), 101–111.
[11] O. Favaron, T. W. Haynes, S. T. Hedetniemi, Domination subdivision numbers in graphs, Util. Math. 66 (2004), 195–209.
[12] T. W. Haynes, M. A. Henning, L. S. Hopkins, Total domination subdivision numbers of graphs, Discuss. Math. Graph Theory 24 (2004), 457–467. 
[13] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, J. Knisely, L.C. van der Merwe, Domination subdivision numbers, Discuss. Math. Graph Theory 21 (2001) 239–253.
[14] T. W. Haynes, S. T. Hedetniemi, P. J. Slater. Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[15] M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004), 181–188.
[16] M. Lemańska, Nordhaus-Gaddum results for weakly convex domination number of graph, Discuss. Math. Graph Theory 30 (2010), 257–263.
[17] J. Raczek, NP-completeness of weakly convex and convex dominating set decision problems, Opuscula Math. 24 (2004), 189–196.
[18] S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997).
 

Files

Share

How to cite

Statistics