Critical graphs with respect to total domination and connected domination
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-γc-critical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < k for every uv /∈ E(G). Further, a k-tvc graph is a graph with γt(G) = k a...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Centre for Discrete Mathematics and Computing
2016
|
| Online Access: | http://hdl.handle.net/20.500.11937/15897 |
| _version_ | 1848749019009908736 |
|---|---|
| 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 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-γc-critical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < k for every uv /∈ E(G). Further, a k-tvc graph is a graph with γt(G) = k and γt (G − v) < k for all v ∈ V(G), where v is not a support vertex (i.e. all neighbors of v have degree greater than one). A 2-connected graph G is said to be k-cvc if γc(G) = k and γc (G − v) < k for all v ∈ V(G). In this paper, we prove that connected k-γt -critical graphs and k-γc-critical graphs are the same if and only if 3 ≤ k ≤ 4. For k ≥ 5, we concentrate on the class of connected k-γt-critical graphs G with γc (G) = k and the class of k-γc-critical graphs G with γt(G) = k. We show that these classes intersect but they do not need to be the same. Further, we prove that 2-connected k-tvc graphs and k-cvc graphs are the same if and only if 3 ≤ k ≤ 4. Similarly, for k ≥ 5, we focus on the class of 2-connected k-tvc graphs G with γc (G) = k and the class of 2-connected k-cvc graphs G with γt (G) = k. We finish this paper by showing that these classes do not need to be the same. |
| first_indexed | 2025-11-14T07:14:16Z |
| format | Journal Article |
| id | curtin-20.500.11937-15897 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:14:16Z |
| publishDate | 2016 |
| publisher | Centre for Discrete Mathematics and Computing |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-158972017-01-30T11:52:35Z Critical graphs with respect to total domination and connected domination Kaemawichanurat, P. Caccetta, Louis Ananchuen, N. 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-γc-critical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < k for every uv /∈ E(G). Further, a k-tvc graph is a graph with γt(G) = k and γt (G − v) < k for all v ∈ V(G), where v is not a support vertex (i.e. all neighbors of v have degree greater than one). A 2-connected graph G is said to be k-cvc if γc(G) = k and γc (G − v) < k for all v ∈ V(G). In this paper, we prove that connected k-γt -critical graphs and k-γc-critical graphs are the same if and only if 3 ≤ k ≤ 4. For k ≥ 5, we concentrate on the class of connected k-γt-critical graphs G with γc (G) = k and the class of k-γc-critical graphs G with γt(G) = k. We show that these classes intersect but they do not need to be the same. Further, we prove that 2-connected k-tvc graphs and k-cvc graphs are the same if and only if 3 ≤ k ≤ 4. Similarly, for k ≥ 5, we focus on the class of 2-connected k-tvc graphs G with γc (G) = k and the class of 2-connected k-cvc graphs G with γt (G) = k. We finish this paper by showing that these classes do not need to be the same. 2016 Journal Article http://hdl.handle.net/20.500.11937/15897 Centre for Discrete Mathematics and Computing restricted |
| spellingShingle | Kaemawichanurat, P. Caccetta, Louis Ananchuen, N. Critical graphs with respect to total domination and connected domination |
| title | Critical graphs with respect to total domination and connected domination |
| title_full | Critical graphs with respect to total domination and connected domination |
| title_fullStr | Critical graphs with respect to total domination and connected domination |
| title_full_unstemmed | Critical graphs with respect to total domination and connected domination |
| title_short | Critical graphs with respect to total domination and connected domination |
| title_sort | critical graphs with respect to total domination and connected domination |
| url | http://hdl.handle.net/20.500.11937/15897 |