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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.