On minimum cutsets in independent domination vertex-critical graphs
Access Status
Authors
Date
2018Type
Metadata
Show full item recordCitation
Source Title
ISSN
School
Collection
Abstract
© 2018, University of Queensland. All rights reserved. Let ? i (G) denote the independent domination number of G. A graph G is said to be k-? i -vertex-critical if ? i (G) = k and for each x ? V (G), ? i (G - x) < k. In this paper, we show that for any k-? i -vertex-critical graph H of order n with k = 3, there exists an n-connected k-? i -vertex-critical graph G H containing H as an induced subgraph. Consequently, there are infinitely many non-isomorphic connected k-? i -vertex-critical graphs. We also establish a number of properties of connected 3-? i -vertex-critical graphs. In particular, we derive an upper bound on ?(G-S), the number of components of G-S when G is a connected 3-? i -vertex-critical graph and S is a minimum cutset of G with |S| = 3.
Related items
Showing items related by title, author, creator and subject.
-
Kaemawichanurat, P.; Caccetta, Louis; Ananchuen, N. (2018)A vertex subset D of G is a dominating set of G if every vertex in V(G)-D is adjacent to a vertex in D. Moreover, a dominating set D of G is a connected dominating set if G[D] is connected. The minimum cardinality of a ...
-
Ananchuen, Nawarat (1994)Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n - 1, G is said to be k-extendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...
-
Ananchuen, N.; Ananchuen, W.; Caccetta, Louis (2017)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 ...