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) < 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 [...] improving a result proved by Ao [3], where ω(G−S) denotes the number of components of G−S. We also provide a characteriza- tion 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.
@article{bwmeta1.element.doi-10_7151_dmgt_1828,
author = {Nawarat Ananchuen and Watcharaphong Ananchuen},
title = {Some Toughness Results in Independent Domination Critical Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {703-713},
zbl = {1326.05102},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1828}
}
Nawarat Ananchuen; Watcharaphong Ananchuen. Some Toughness Results in Independent Domination Critical Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 703-713. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1828/
[1] N. Ananchuen and W. Ananchuen, A characterization of independent domination critical graphs with a cutvertex , J. Combin. Math. Combin. Comput. (to appear). | Zbl 06587652
[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). | Zbl 1201.05002
[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 [Crossref] | Zbl 0512.05055