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

Abstract

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

How to cite

top

Nawarat 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. [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. [2] N. Ananchuen, W. Ananchuen and L. Caccetta, A characterization of connected 3-i-critical graphs of connectivity two, (2014) submitted. 
  3. [3] S. Ao, Independent Domination Critical Graphs, Master Thesis (University of Victoria, 1994). 
  4. [4] M. Dehmer, (Ed.), Structural Analysis of Complex Networks (Birkhauser, Bre- ingsville, 2011). Zbl1201.05002
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Eds), Domination in Graphs: Ad- vanced Topics (Marcel Dekker, New York, 1998). 
  6. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.