Bounds on the order of connected domination vertex critical graphs
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 connected dominating set of G is called the connected domination number of G and...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2018
|
| Online Access: | http://hdl.handle.net/20.500.11937/74215 |
| _version_ | 1848763211222876160 |
|---|---|
| author | Kaemawichanurat, P. Caccetta, Louis Ananchuen, N. |
| author_facet | Kaemawichanurat, P. Caccetta, Louis Ananchuen, N. |
| author_sort | Kaemawichanurat, P. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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 connected dominating set of G is called the connected domination number of G and is denoted by yc(G). A graph G is said to be fc-yc-vertex critical if yc(G) = k and yc(G-v) < k for any vertex v of G. In this paper, we establish the order of k-yc-vertex critical graphs in terms of k and the maximum degree A. We prove that a Jt-yc.-vertexcritical graph has A + k<n< (A-l)(k-l) + 3 vertices. Further, the upper bound is sharp for all integers k > 3 when A is even. It has been proved that every k-yc-vertex critical graph achieving the upper bound is A-regular for k = 2 or 3. For k = 4, we prove that every 4-yc-vertex critical graph achieving the upper bound is A-regular. We further show that, for k = 2,3 or 4, there exists a Jt-yc-vertex critical graph of order (A-l)(fc-l) + 3 if and only if A is even. We characterize, for k > 5, that every k-yc-vertex critical graph of order A + k is isomorphic to the cycle of length k + 2. |
| first_indexed | 2025-11-14T10:59:51Z |
| format | Journal Article |
| id | curtin-20.500.11937-74215 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T10:59:51Z |
| publishDate | 2018 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-742152019-08-22T07:05:32Z Bounds on the order of connected domination vertex critical graphs Kaemawichanurat, P. Caccetta, Louis Ananchuen, N. 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 connected dominating set of G is called the connected domination number of G and is denoted by yc(G). A graph G is said to be fc-yc-vertex critical if yc(G) = k and yc(G-v) < k for any vertex v of G. In this paper, we establish the order of k-yc-vertex critical graphs in terms of k and the maximum degree A. We prove that a Jt-yc.-vertexcritical graph has A + k<n< (A-l)(k-l) + 3 vertices. Further, the upper bound is sharp for all integers k > 3 when A is even. It has been proved that every k-yc-vertex critical graph achieving the upper bound is A-regular for k = 2 or 3. For k = 4, we prove that every 4-yc-vertex critical graph achieving the upper bound is A-regular. We further show that, for k = 2,3 or 4, there exists a Jt-yc-vertex critical graph of order (A-l)(fc-l) + 3 if and only if A is even. We characterize, for k > 5, that every k-yc-vertex critical graph of order A + k is isomorphic to the cycle of length k + 2. 2018 Journal Article http://hdl.handle.net/20.500.11937/74215 Elsevier restricted |
| spellingShingle | Kaemawichanurat, P. Caccetta, Louis Ananchuen, N. Bounds on the order of connected domination vertex critical graphs |
| title | Bounds on the order of connected domination vertex critical graphs |
| title_full | Bounds on the order of connected domination vertex critical graphs |
| title_fullStr | Bounds on the order of connected domination vertex critical graphs |
| title_full_unstemmed | Bounds on the order of connected domination vertex critical graphs |
| title_short | Bounds on the order of connected domination vertex critical graphs |
| title_sort | bounds on the order of connected domination vertex critical graphs |
| url | http://hdl.handle.net/20.500.11937/74215 |