On minimum cutsets in independent domination vertex-critical graphs
© 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 orde...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Centre for Discrete Mathematics & Computing
2018
|
| Online Access: | http://hdl.handle.net/20.500.11937/68903 |
| _version_ | 1848761918183964672 |
|---|---|
| author | Ananchuen, N. Ruangthampisan, S. Ananchuen, W. Caccetta, Louis |
| author_facet | Ananchuen, N. Ruangthampisan, S. Ananchuen, W. Caccetta, Louis |
| author_sort | Ananchuen, N. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | © 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. |
| first_indexed | 2025-11-14T10:39:18Z |
| format | Journal Article |
| id | curtin-20.500.11937-68903 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T10:39:18Z |
| publishDate | 2018 |
| publisher | Centre for Discrete Mathematics & Computing |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-689032018-06-29T12:27:36Z On minimum cutsets in independent domination vertex-critical graphs Ananchuen, N. Ruangthampisan, S. Ananchuen, W. Caccetta, Louis © 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. 2018 Journal Article http://hdl.handle.net/20.500.11937/68903 Centre for Discrete Mathematics & Computing restricted |
| spellingShingle | Ananchuen, N. Ruangthampisan, S. Ananchuen, W. Caccetta, Louis On minimum cutsets in independent domination vertex-critical graphs |
| title | On minimum cutsets in independent domination vertex-critical graphs |
| title_full | On minimum cutsets in independent domination vertex-critical graphs |
| title_fullStr | On minimum cutsets in independent domination vertex-critical graphs |
| title_full_unstemmed | On minimum cutsets in independent domination vertex-critical graphs |
| title_short | On minimum cutsets in independent domination vertex-critical graphs |
| title_sort | on minimum cutsets in independent domination vertex-critical graphs |
| url | http://hdl.handle.net/20.500.11937/68903 |