# Some Toughness Results in Independent Domination Critical Graphs

Nawarat Ananchuen; Watcharaphong Ananchuen

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 4, page 703-713
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topNawarat Ananchuen, and Watcharaphong Ananchuen. "Some Toughness Results in Independent Domination Critical Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 703-713. <http://eudml.org/doc/275986>.

@article{NawaratAnanchuen2015,

abstract = {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.},

author = {Nawarat Ananchuen, Watcharaphong Ananchuen},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination critical; toughness},

language = {eng},

number = {4},

pages = {703-713},

title = {Some Toughness Results in Independent Domination Critical Graphs},

url = {http://eudml.org/doc/275986},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Nawarat Ananchuen

AU - Watcharaphong Ananchuen

TI - Some Toughness Results in Independent Domination Critical Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 4

SP - 703

EP - 713

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

LA - eng

KW - domination critical; toughness

UR - http://eudml.org/doc/275986

ER -

## References

top- [1] N. Ananchuen and W. Ananchuen, A characterization of independent domination critical graphs with a cutvertex , J. Combin. Math. Combin. Comput. (to appear). Zbl06587652
- [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). Zbl1201.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] Zbl0512.05055

## NotesEmbed ?

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