Geodesic
Matchings and total domination subdivision number in graphs with few induced 4-cycles
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 611-618.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: matching, barrier, total domination number, total domination subdivision number 
@article{DMGT_2010_30_4_a6,
     author = {Favaron, Odile and Karami, Hossein and Khoeilar, Rana and Sheikholeslami, Seyed},
     title = {Matchings and total domination subdivision number in graphs with few induced 4-cycles},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {611--618},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a6/}
}
TY  - JOUR
AU  - Favaron, Odile
AU  - Karami, Hossein
AU  - Khoeilar, Rana
AU  - Sheikholeslami, Seyed
TI  - Matchings and total domination subdivision number in graphs with few induced 4-cycles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 611
EP  - 618
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a6/
LA  - en
ID  - DMGT_2010_30_4_a6
ER  - 
%0 Journal Article
%A Favaron, Odile
%A Karami, Hossein
%A Khoeilar, Rana
%A Sheikholeslami, Seyed
%T Matchings and total domination subdivision number in graphs with few induced 4-cycles
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 611-618
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a6/
%G en
%F DMGT_2010_30_4_a6
Favaron, Odile; Karami, Hossein; Khoeilar, Rana; Sheikholeslami, Seyed. Matchings and total domination subdivision number in graphs with few induced 4-cycles. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 611-618. http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a6/

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

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

[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).

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

[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).

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

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

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

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

[10] [10]. H. Karami, A. Khodkar and S.M. Sheikholeslami, An upper bound for total domination subdivision numbers of graphs, Ars Combin. (to appear).

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

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

[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).