The convex domination subdivision number of a graph - Publication - Bridge of Knowledge

Your account

login

Search

The convex domination subdivision number of a graph

Abstract

Let G = (V;E) be a simple graph. A set D\subset V is a dominating set of G if every vertex in V - 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\subset 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 convex domination number \gamma_con(G) of a graph G equals the minimum cardinality of a convex dominating set in G. The convex domination subdivision number sd_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.

Citations

  • 0

    CrossRef

  • 0

    Web of Science

  • 1 1

    Scopus

Authors (4)

Cite as

Full text

download paper
downloaded 37 times
Publication version
Accepted or Published Version
License
Creative Commons: CC-BY-SA open in new tab

Keywords

Details

Category:
Articles
Type:
publikacja w in. zagranicznym czasopiśmie naukowym (tylko język obcy)
Published in:
Communications in Combinatorics and Optimization no. 1, pages 43 - 56,
ISSN: 2538-2128
Language:
English
Publication year:
2016
Bibliographic description:
Dettlaff M., Lemańska M., Kosary S., Sheikholeslami S.. The convex domination subdivision number of a graph. Communications in Combinatorics and Optimization, 2016, Vol. 1, nr. 1, s.43-56
DOI:
Digital Object Identifier (open in new tab) 10.22049/cco.2016.13544
Bibliography: test
  1. ∩ N G (u 1 ). Therefore {u 2 , x 2 , u 3 , w} ⊆ D 2 . Since D 2 is a convex set and since G is triangle-free, u 4 is not dominated by the set {u 2 , x 2 , u 3 , w} implying that |D 2 | ≥ 5 as desired. open in new tab
  2. Since G is triangle-free and N G (u 2 ) ∩ N G (u 4 ) = {u 3 }, we have d G (u 2 , u 4 ) ≥ 3. If d G (u 2 , u 4 ) ≥ 4, then it follows from convexity of D 2 that |D 2 | ≥ 5 and we are done. Let d G (u 2 , u 4 ) = 3 and let Q = u 2 w 1 w 2 u 4 is a path with length 3 in G . Then {u 2 , w 1 , w 2 , u 4 } ⊆ D 2 . Since u 1 u 4 ∈ E(G), d G (u 1 , u 4 ) = 3 and G is triangle-free, we deduce that u 1 is not dominated by {u 2 , w 1 , w 2 , u 4 } implying dominating set of G which is a contradiction. Henceforth, assume u i has a private neighbor with respect to D, say v i , for each i. Let G be the graph obtained from G by subdividing the edges u 1 v 1 , u 2 v 2 , u 3 v 3 with vertices x 1 , x 2 , x 3 , respectively, and let D 3 be a γ con (G )-set. We show that |D 3 | ≥ 5. Assume, to the contrary, that |D 3 | ≤ 4. To dominate x i , we must have D 3 ∩ {u i , v i } = ∅ for each i. If {u i , v i } ⊆ D 3 for some i, then x i ∈ D 3 implying that |D 3 | ≥ 5, a contradiction. Let |{u i , v i } ∩ D 3 | = 1 for each i. Now we consider the following subcases. open in new tab
  3. Let D 3 = {v 1 , v 2 , v 3 , w}. Then w must be adjacent to u i for each i. Since G [D 3 ] is connected, we may assume that wv 1 ∈ E(G). This leads to a contradiction because G is triangle-free and the proof is complete. open in new tab
  4. H. Aram, S. M. Sheikholeslami, O. Favaron, Domination subdivision num- bers of trees, Discrete Math. 309 ( 2009), 622-628. open in new tab
  5. M. Atapour, S. M. Sheikholeslami, A. Khodkar, Roman domination sub- division number of graphs, Aequationes Math. 78 (2009), 237-245. open in new tab
  6. M. Atapour, S. M. Sheikholeslami, A. Hansberg, L. Volkmann, A. Khod- kar, 2-domination subdivision number of graphs, AKCE J. Graphs. Com- bin. 5 (2008), 165-173. open in new tab
  7. J. Cyman, M. Lemańska, J. Raczek, Graphs with convex domination number close to their order, Discuss. Math. Graph Theory 26 (2006), 307- 316. open in new tab
  8. N. Dehgardi, S.M. Sheikholeslami, L. Volkmann, The rainbow domination subdivision numbers of graphs, Mat. Vesnik 67 (2015), 102-114. open in new tab
  9. M. Dettlaff, M. Lemańska, S. Kosary, S. M. Sheikholeslami, Weakly convex domination subdivision number of a graph, Filomat (To appear) open in new tab
  10. M. Dettlaff, M. Lemańska, Influence of edge subdivision on the convex domination number, Australas. J. Combin. 53 (2012), 19-30. open in new tab
  11. M. Falahat, S.M. Sheikholeslami, L. Volkmann, New bounds on the rain- bow domination subdivision number, Filomat 28 (2014), 615-622. open in new tab
  12. O. Fvaron, H. Karami, S.M. Sheikholeslami, Disprove of a conjecture the domination subdivision number of a graph, Graphs Combin. 24 (2008), 309-312. open in new tab
  13. O. Favaron, H. Karami, S. M. Sheikholeslami, Connected domination subdivision numbers of graphs, Util. Math. 77 (2008), 101-111. open in new tab
  14. O. Favaron, T. W. Haynes, S. T. Hedetniemi, Domination subdivision numbers in graphs, Util. Math. 66 (2004), 195-209.
  15. T. W. Haynes, M. A. Henning, L. S. Hopkins, Total domination subdivi- sion numbers of graphs, Discuss. Math. Graph Theory 24 (2004), 457-467. open in new tab
  16. 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. open in new tab
  17. T. W. Haynes, S. T. Hedetniemi, P. J. Slater. Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998 open in new tab
  18. M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004), 181-188.
  19. M. Lemańska, Nordhaus-Gaddum results for weakly convex domination number of graph, Discuss. Math. Graph Theory 30 (2010), 257-263. open in new tab
  20. J. Raczek, NP-completeness of weakly convex and convex dominating set decision problems, Opuscula Math. 24 (2004), 189-196.
  21. S. Velammal, Studies in Graph Theory: Covering, Independence, Domina- tion and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar Uni- versity, Tirunelveli, 1997).
Verified by:
Gdańsk University of Technology

seen 196 times

Recommended for you

Weakly convex domination subdivision number of a graph

2016

Weakly convex and convex domination numbers of some products of graphs

2016

Influence of edge subdivision on the convex domination number

2012

On trees with double domination number equal to 2-outer-independent domination number plus one

2012
Meta Tags