Connected Domination Critical Graphs with Cut Vertices
A graph G is said to be k- γc-critical if the connected domination number of G, γc(G), is k and γc(G + uv) < k for any pair of non-adjacent vertices u and v of G. Let G be a k-γc-critical graph and ζ (G) the number of cut vertices of G. It was proved, in [1, 6], that, for 3 ≤ k ≤ 4, every k-γc-cr...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2020-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2163 |
| _version_ | 1797713171485556736 |
|---|---|
| author | Kaemawichanurat Pawaton Ananchuen Nawarat |
| author_facet | Kaemawichanurat Pawaton Ananchuen Nawarat |
| author_sort | Kaemawichanurat Pawaton |
| collection | DOAJ |
| description | A graph G is said to be k- γc-critical if the connected domination number of G, γc(G), is k and γc(G + uv) < k for any pair of non-adjacent vertices u and v of G. Let G be a k-γc-critical graph and ζ (G) the number of cut vertices of G. It was proved, in [1, 6], that, for 3 ≤ k ≤ 4, every k-γc-critical graph satisfies ζ (G) ≤ k − 2. In this paper, we generalize that every k-γc-critical graph satisfies ζ (G) ≤ k − 2 for all k ≥ 5. We also characterize all k-γc-critical graphs when ζ(G) is achieving the upper bound. |
| first_indexed | 2024-03-12T07:32:40Z |
| format | Article |
| id | doaj.art-c4324cc008764efe9d8d2befb6de2e74 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:40Z |
| publishDate | 2020-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-c4324cc008764efe9d8d2befb6de2e742023-09-02T21:43:03ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922020-11-014041035105510.7151/dmgt.2163dmgt.2163Connected Domination Critical Graphs with Cut VerticesKaemawichanurat Pawaton0Ananchuen Nawarat1Theoretical and Computational Science Center, Science Laboratory Building and Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, 126 Pracha Uthit Road, Bang Mod Thung Khru, Bangkok 10140, ThailandCenter of Excellence in Mathematics, CHE, Si Ayutthaya Rd., Bangkok 10400, ThailandA graph G is said to be k- γc-critical if the connected domination number of G, γc(G), is k and γc(G + uv) < k for any pair of non-adjacent vertices u and v of G. Let G be a k-γc-critical graph and ζ (G) the number of cut vertices of G. It was proved, in [1, 6], that, for 3 ≤ k ≤ 4, every k-γc-critical graph satisfies ζ (G) ≤ k − 2. In this paper, we generalize that every k-γc-critical graph satisfies ζ (G) ≤ k − 2 for all k ≥ 5. We also characterize all k-γc-critical graphs when ζ(G) is achieving the upper bound.https://doi.org/10.7151/dmgt.2163connected dominationcritical05c69 |
| spellingShingle | Kaemawichanurat Pawaton Ananchuen Nawarat Connected Domination Critical Graphs with Cut Vertices Discussiones Mathematicae Graph Theory connected domination critical 05c69 |
| title | Connected Domination Critical Graphs with Cut Vertices |
| title_full | Connected Domination Critical Graphs with Cut Vertices |
| title_fullStr | Connected Domination Critical Graphs with Cut Vertices |
| title_full_unstemmed | Connected Domination Critical Graphs with Cut Vertices |
| title_short | Connected Domination Critical Graphs with Cut Vertices |
| title_sort | connected domination critical graphs with cut vertices |
| topic | connected domination critical 05c69 |
| url | https://doi.org/10.7151/dmgt.2163 |
| work_keys_str_mv | AT kaemawichanuratpawaton connecteddominationcriticalgraphswithcutvertices AT ananchuennawarat connecteddominationcriticalgraphswithcutvertices |