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/