On the total domination subdivision numbers in graphs

Seyed Sheikholeslami

Open Mathematics (2010)

  • Volume: 8, Issue: 3, page 468-473
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Seyed Sheikholeslami. "On the total domination subdivision numbers in graphs." Open Mathematics 8.3 (2010): 468-473. <http://eudml.org/doc/269209>.

@article{SeyedSheikholeslami2010,
abstract = {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.},
author = {Seyed Sheikholeslami},
journal = {Open Mathematics},
keywords = {Total domination number; Total domination subdivision number; total domination number; total domination subdivision number},
language = {eng},
number = {3},
pages = {468-473},
title = {On the total domination subdivision numbers in graphs},
url = {http://eudml.org/doc/269209},
volume = {8},
year = {2010},
}

TY - JOUR
AU - Seyed Sheikholeslami
TI - On the total domination subdivision numbers in graphs
JO - Open Mathematics
PY - 2010
VL - 8
IS - 3
SP - 468
EP - 473
AB - 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.
LA - eng
KW - Total domination number; Total domination subdivision number; total domination number; total domination subdivision number
UR - http://eudml.org/doc/269209
ER -

References

top
  1. [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 Zbl1211.05109
  2. [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 Zbl1198.05121
  3. [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 Zbl1217.05178
  4. [4] Favaron O., Karami H., Sheikholeslami S.M., Total domination and total domination subdivision numbers, Australas. J. Combin., 2007, 38,229-235 Zbl1133.05068
  5. [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 Zbl1213.90212
  6. [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 Zbl1020.05048
  7. [7] Haynes T.W., Henning M.A., Hopkins L.S., Total domination subdivision numbers of graphs, Discuss. Math. Graph Theory, 2004, 24, 457–467 Zbl1065.05070
  8. [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 Zbl1054.05076
  9. [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 Zbl1168.05050
  10. [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 Zbl1205.05169
  11. [11] Karami H., Khodkar A., Sheikholeslami S.M., An upper bound for total domination subdivision numbers of graphs, Ars Combin., to appear Zbl1265.05462
  12. [12] Velammal S., Studies in Graph Theory: Covering, Independence, Domination and Related Topics, PhD Thesis, Manonmaniam Sundaranar University, Tirunelveli, 1997 
  13. [13] West D.B., Introduction to Graph Theory, 2nd ed., Prentice-Hall, Inc, USA, 2000 

NotesEmbed ?

top

You must be logged in to post comments.