On minimum cutsets in independent domination vertexcritical graphs
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 vertexcritical if ? i (G) = k and for each x ? V (G), ? i (G  x) < k. In this paper, we show that for any k? i vertexcritical graph H of order n with k = 3, there exists an nconnected k? i vertexcritical graph G H containing H as an induced subgraph. Consequently, there are infinitely many nonisomorphic connected k? i vertexcritical graphs. We also establish a number of properties of connected 3? i vertexcritical graphs. In particular, we derive an upper bound on ?(GS), the number of components of GS when G is a connected 3? i vertexcritical graph and S is a minimum cutset of G with S = 3.
Citation
Source Title
ISSN
School
Collection
Related items
Showing items related by title, author, creator and subject.

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

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 kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...

Kaemawichanurat, P.; Caccetta, Louis; Ananchuen, N. (2016)A graph G is said to be kγt critical if the total domination number γt(G)= k and γt (G + uv) < k for every uv /∈ E(G). A kγccritical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < ...