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:
PDF