A characterization of 3-i-critical graphs of connectivity two
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/20.500.11937/59557 |
| _version_ | 1848760512160989184 |
|---|---|
| author | Ananchuen, N. Ananchuen, W. Caccetta, Louis |
| author_facet | Ananchuen, N. Ananchuen, W. Caccetta, Louis |
| author_sort | Ananchuen, N. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. The problem that arises is that of characterizing k-i critical graphs. In this paper, we characterize connected 3-i-critical graphs with minimum vertex cutset of size 2. More specifically, we show that if G is a connected 3-i-critical graph with minimum vertex cutset S of size 2 and the number of components of G - S is exactly two, then G is isomorphic to a graph in one of nine classes of connected 3-i-critical graphs. The results in this paper together with results in [1] and [2] provide a complete characterization of connected 3-i-critical graphs with a minimum cutset of size at most 3. |
| first_indexed | 2025-11-14T10:16:57Z |
| format | Journal Article |
| id | curtin-20.500.11937-59557 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T10:16:57Z |
| publishDate | 2017 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-595572018-03-26T01:08:58Z A characterization of 3-i-critical graphs of connectivity two Ananchuen, N. Ananchuen, W. Caccetta, Louis 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. The problem that arises is that of characterizing k-i critical graphs. In this paper, we characterize connected 3-i-critical graphs with minimum vertex cutset of size 2. More specifically, we show that if G is a connected 3-i-critical graph with minimum vertex cutset S of size 2 and the number of components of G - S is exactly two, then G is isomorphic to a graph in one of nine classes of connected 3-i-critical graphs. The results in this paper together with results in [1] and [2] provide a complete characterization of connected 3-i-critical graphs with a minimum cutset of size at most 3. 2017 Journal Article http://hdl.handle.net/20.500.11937/59557 10.2989/16073606.2017.1336653 restricted |
| spellingShingle | Ananchuen, N. Ananchuen, W. Caccetta, Louis A characterization of 3-i-critical graphs of connectivity two |
| title | A characterization of 3-i-critical graphs of connectivity two |
| title_full | A characterization of 3-i-critical graphs of connectivity two |
| title_fullStr | A characterization of 3-i-critical graphs of connectivity two |
| title_full_unstemmed | A characterization of 3-i-critical graphs of connectivity two |
| title_short | A characterization of 3-i-critical graphs of connectivity two |
| title_sort | characterization of 3-i-critical graphs of connectivity two |
| url | http://hdl.handle.net/20.500.11937/59557 |