Some Toughness Results in Independent Domination Critical Graphs

• Autorzy: Nawarat Ananchuen , Watcharaphong Ananchuen
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

domination critical; toughness

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 4
• Strony: 703-713

Daty

wydano

2015-11-01

otrzymano

2013-10-15

poprawiono

2015-02-23

zaakceptowano

2015-02-23

online

2015-11-10

Twórcy

autor

Nawarat Ananchuen

• Department of Mathematics, Faculty of Science Silpakorn University Nakorn Pathom 73000, Thailand Centre of Excellence in Mathematics CHE, Si Ayutthaya Rd. Bangkok 10400, Thailand

autor

Watcharaphong Ananchuen

• School of Liberal Arts Sukhothai Thammathirat Open University Pakkred, Nonthaburi 11120, Thailand

Bibliografia

• [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 [Crossref]

Identyfikatory

DOI

10.7151/dmgt.1828