PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2010 | 8 | 3 | 468-473
Tytuł artykułu

On the total domination subdivision numbers in graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (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 total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sdγ t(G) ≤ 2γ t(G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sdγ t(G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sdγ t(G)=2γt(G)−1.
Wydawca
Czasopismo
Rocznik
Tom
8
Numer
3
Strony
468-473
Opis fizyczny
Daty
wydano
2010-06-01
online
2010-05-30
Twórcy
Bibliografia
  • [1] Favaron O., Karami H., Khoeilar R., Sheikholeslami S.M., A new upper bound for total domination subdivision numbers, Graphs Combin., 2009, 25, 41–47 http://dx.doi.org/10.1007/s00373-008-0824-6
  • [2] Favaron O., Karami H., Khoeilar R., Sheikholeslami S.M., On the total domination subdivision number in some classes of graphs, J. Comb. Optim., Doi: 10.1007/s10878-008-9193-6
  • [3] Favaron O., Karami H., Khoeilar R., Sheikholeslami S.M., Matchings and total domination subdivision number in graphs with few induced 4-cycles, Discuss. Math. Graph Theory, to appear
  • [4] Favaron O., Karami H., Sheikholeslami S.M., Total domination and total domination subdivision numbers, Australas. J. Combin., 2007, 38,229-235
  • [5] Favaron O., Karami H., Sheikholeslami S.M., Bounding the total domination subdivision number of a graph in terms of its order, J. Comb. Optim., Doi: 10.1007/s10878-009-9224-y
  • [6] Haynes T.W., Hedetniemi S.T., van der Merwe L.C., Total domination subdivision numbers, J. Combin. Math. Combin. Comput., 2003, 44, 115–128
  • [7] Haynes T.W., Henning M.A., Hopkins L.S., Total domination subdivision numbers of graphs, Discuss. Math. Graph Theory, 2004, 24, 457–467
  • [8] Haynes T.W., Henning M.A., Hopkins L.S., Total domination subdivision numbers of trees, Discrete Math., 2004, 286, 195–202 http://dx.doi.org/10.1016/j.disc.2004.06.004
  • [9] Karami H., Khodkar A., Khoeilar R., Sheikholeslami S.M., Trees whose total domination subdivision number is one, Bull. Inst. Combin. Appl., 2008, 53, 57–67
  • [10] Karami H., Khodkar A., Khoeilar R., Sheikholeslami S.M., An upper bound for the total domination subdivision number of a graph, Graphs Combin., 2009, 25, 727–733 http://dx.doi.org/10.1007/s00373-010-0877-1
  • [11] Karami H., Khodkar A., Sheikholeslami S.M., An upper bound for total domination subdivision numbers of graphs, Ars Combin., to appear
  • [12] Velammal S., Studies in Graph Theory: Covering, Independence, Domination and Related Topics, PhD Thesis, Manonmaniam Sundaranar University, Tirunelveli, 1997
  • [13] West D.B., Introduction to Graph Theory, 2nd ed., Prentice-Hall, Inc, USA, 2000
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-010-0020-9
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.