Authors: N. Ananchuen, P. Kaemawichanurat Title: Connected domination critical graphs with cut vertices Source: Discussiones Mathematicae Graph Theory Received 12.12.2017, Revised 26.06.2018, Accepted 26.06.2018, doi: 10.7151/dmgt.2163 | |
Abstract: 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 \cite{A, PKNA}, 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. | |
Keywords: connected domination, critical | |
Links: |