Geodesic
Some Toughness Results in Independent Domination Critical Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 703-713.

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

A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set of G. A graph G is k-i-critical if i(G) = k, but i(G+uv) lt; k for any pair of non-adjacent vertices u and v of G. In this paper, we establish that if G is a connected 3-i-critical graph and S is a vertex cutset of G with |S| ≥ 3, then ω ( G - S ) ≤1+√(8|S|+1)/2, improving a result proved by Ao [3], where ω(G−S) denotes the number of components of G−S. We also provide a characterization of the connected 3-i-critical graphs G attaining the maximum number of ω(G − S) when S is a minimum cutset of size 2 or 3.
Keywords: domination critical, toughness 
@article{DMGT_2015_35_4_a8,
     author = {Ananchuen, Nawarat and Ananchuen, Watcharaphong},
     title = {Some {Toughness} {Results} in {Independent} {Domination} {Critical} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {703--713},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a8/}
}
TY  - JOUR
AU  - Ananchuen, Nawarat
AU  - Ananchuen, Watcharaphong
TI  - Some Toughness Results in Independent Domination Critical Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 703
EP  - 713
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a8/
LA  - en
ID  - DMGT_2015_35_4_a8
ER  - 
%0 Journal Article
%A Ananchuen, Nawarat
%A Ananchuen, Watcharaphong
%T Some Toughness Results in Independent Domination Critical Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 703-713
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a8/
%G en
%F DMGT_2015_35_4_a8
Ananchuen, Nawarat; Ananchuen, Watcharaphong. Some Toughness Results in Independent Domination Critical Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 703-713. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a8/

[1] N. Ananchuen and W. Ananchuen, A characterization of independent domination critical graphs with a cutvertex, J. Combin. Math. Combin. Comput. (to appear).

[2] N. Ananchuen, W. Ananchuen and L. Caccetta, A characterization of connected 3-i-critical graphs of connectivity two, (2014) submitted.

[3] S. Ao, Independent Domination Critical Graphs, Master Thesis (University of Victoria, 1994).

[4] M. Dehmer, (Ed.), Structural Analysis of Complex Networks (Birkhauser, Bre- ingsville, 2011).

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Eds), Domination in Graphs: Ad- vanced Topics (Marcel Dekker, New York, 1998).

[6] D.P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory Ser. B 34 (1983) 65-76. doi:10.1016/0095-8956(83)90007-2