Matchings and total domination subdivision number in graphs with few induced 4-cycles

Odile Favaron; Hossein Karami; Rana Khoeilar; Seyed Mahmoud Sheikholeslami

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 4, page 611-618
  • ISSN: 2083-5892

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 γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number s d γ ₜ ( 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. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial Optimization, to appear) conjectured that: For any connected graph G of order n ≥ 3, s d γ ₜ ( G ) ≤ γ ₜ ( G ) + 1 . In this paper we use matchings to prove this conjecture for graphs with at most three induced 4-cycles through each vertex.

How to cite

top

Odile Favaron, et al. "Matchings and total domination subdivision number in graphs with few induced 4-cycles." Discussiones Mathematicae Graph Theory 30.4 (2010): 611-618. <http://eudml.org/doc/270987>.

@article{OdileFavaron2010,
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 γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $sd_\{γₜ(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. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial Optimization, to appear) conjectured that: For any connected graph G of order n ≥ 3, $sd_\{γₜ(G)\} ≤ γₜ(G)+1$. In this paper we use matchings to prove this conjecture for graphs with at most three induced 4-cycles through each vertex.},
author = {Odile Favaron, Hossein Karami, Rana Khoeilar, Seyed Mahmoud Sheikholeslami},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {matching; barrier; total domination number; total domination subdivision number},
language = {eng},
number = {4},
pages = {611-618},
title = {Matchings and total domination subdivision number in graphs with few induced 4-cycles},
url = {http://eudml.org/doc/270987},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Odile Favaron
AU - Hossein Karami
AU - Rana Khoeilar
AU - Seyed Mahmoud Sheikholeslami
TI - Matchings and total domination subdivision number in graphs with few induced 4-cycles
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 4
SP - 611
EP - 618
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 γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $sd_{γₜ(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. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial Optimization, to appear) conjectured that: For any connected graph G of order n ≥ 3, $sd_{γₜ(G)} ≤ γₜ(G)+1$. In this paper we use matchings to prove this conjecture for graphs with at most three induced 4-cycles through each vertex.
LA - eng
KW - matching; barrier; total domination number; total domination subdivision number
UR - http://eudml.org/doc/270987
ER -

References

top
  1. [1]. D. Archdeacon, J. Ellis-Monaghan, D. Fisher, D. Froncek, P.C.B. Lam, S. Seager, B. Wei and R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207-210, doi: 10.1002/jgt.20000. Zbl1041.05057
  2. [2]. O. Favaron, H. Karami, R. Khoeilar and S.M. Sheikholeslami, A new upper bound for total domination subdivision numbers, Graphs and Combinatorics 25 (2009) 41-47, doi: 10.1007/s00373-008-0824-6. Zbl1211.05109
  3. [3]. O. Favaron, H. Karami, R. Khoeilar and S.M. Sheikholeslami, On the total domination subdivision number in some classes of graphs, Journal of Combinatorial Optimization, (to appear). Zbl1198.05121
  4. [4]. O. Favaron, H. Karami and S.M. Sheikholeslami, Total domination and total domination subdivision numbers of graphs, Australas. J. Combin. 38 (2007) 229-235. Zbl1133.05068
  5. [5]. O. Favaron, H. Karami and S.M. Sheikholeslami, Bounding the total domination subdivision number of a graph in terms of its order, Journal of Combinatorial Optimization, (to appear). Zbl1213.90212
  6. [6]. T.W. Haynes, M.A. Henning and L.S. Hopkins, Total domination subdivision numbers of graphs, Discuss. Math. Graph Theory 24 (2004) 457-467, doi: 10.7151/dmgt.1244. Zbl1065.05070
  7. [7]. T.W. Haynes, M.A. Henning and L.S. Hopkins, Total domination subdivision numbers of trees, Discrete Math. 286 (2004) 195-202, doi: 10.1016/j.disc.2004.06.004. Zbl1054.05076
  8. [8]. T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003) 115-128. Zbl1020.05048
  9. [9]. M.A. Henning, L. Kang, E. Shan and A. Yeo, On matching and total domination in graphs, Discrete Math. 308 (2008) 2313-2318, doi: 10.1016/j.disc.2006.10.024. Zbl1145.05042
  10. [10]. H. Karami, A. Khodkar and S.M. Sheikholeslami, An upper bound for total domination subdivision numbers of graphs, Ars Combin. (to appear). Zbl1265.05462
  11. [11]. H. Karami, A. Khodkar, R. Khoeilar and S.M. Sheikholeslami, Trees whose total domination subdivision number is one, Bulletin of the Institute of Combinatorics and its Applications, 53 (2008) 57-67. Zbl1168.05050
  12. [12]. L. Lovász and M.D. Plummer, Matching Theory, Annals of Discrete Math 29 (North Holland, 1886). 
  13. [13]. W.T. Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947) 107-111, doi: 10.1112/jlms/s1-22.2.107. Zbl0029.23301
  14. [14]. S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997). 
  15. [15]. D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc, 2000). 

NotesEmbed ?

top

You must be logged in to post comments.