The convex domination subdivision number of a graph - Publikacja - MOST Wiedzy

Twoje konto

zaloguj

Wyszukiwarka

The convex domination subdivision number of a graph

Abstrakt

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.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 1 1

    Scopus

Autorzy (4)

Cytuj jako

Pełna treść

pobierz publikację
pobrano 37 razy
Wersja publikacji
Accepted albo Published Version
Licencja
Creative Commons: CC-BY-SA otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
publikacja w in. zagranicznym czasopiśmie naukowym (tylko język obcy)
Opublikowano w:
Communications in Combinatorics and Optimization nr 1, strony 43 - 56,
ISSN: 2538-2128
Język:
angielski
Rok wydania:
2016
Opis bibliograficzny:
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:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.22049/cco.2016.13544
Bibliografia: 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. otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  4. H. Aram, S. M. Sheikholeslami, O. Favaron, Domination subdivision num- bers of trees, Discrete Math. 309 ( 2009), 622-628. otwiera się w nowej karcie
  5. M. Atapour, S. M. Sheikholeslami, A. Khodkar, Roman domination sub- division number of graphs, Aequationes Math. 78 (2009), 237-245. otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  8. N. Dehgardi, S.M. Sheikholeslami, L. Volkmann, The rainbow domination subdivision numbers of graphs, Mat. Vesnik 67 (2015), 102-114. otwiera się w nowej karcie
  9. M. Dettlaff, M. Lemańska, S. Kosary, S. M. Sheikholeslami, Weakly convex domination subdivision number of a graph, Filomat (To appear) otwiera się w nowej karcie
  10. M. Dettlaff, M. Lemańska, Influence of edge subdivision on the convex domination number, Australas. J. Combin. 53 (2012), 19-30. otwiera się w nowej karcie
  11. M. Falahat, S.M. Sheikholeslami, L. Volkmann, New bounds on the rain- bow domination subdivision number, Filomat 28 (2014), 615-622. otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  13. O. Favaron, H. Karami, S. M. Sheikholeslami, Connected domination subdivision numbers of graphs, Util. Math. 77 (2008), 101-111. otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  17. T. W. Haynes, S. T. Hedetniemi, P. J. Slater. Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998 otwiera się w nowej karcie
  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. otwiera się w nowej karcie
  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).
Weryfikacja:
Politechnika Gdańska

wyświetlono 196 razy

Publikacje, które mogą cię zainteresować

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 Tagi