## Abstract

A set D of vertices in a graph G is a dominating set if every vertex in V(G)−D is adjacent to a vertex in D. If the subgraph induced by the set D is connected, then D is a connected dominating set in G. The connected domination number of G, γ_{c}(G), is the minimum cardinality of a connected dominating set of G. A graph G is k-γ_{c}-critical if γ_{c}(G)=k and γ_{c}(G+uv)<k for every pair of non-adjacent vertices u and v of G. Let G be a k-γ_{c}-critical graph, ζ the number of cut-vertices of G, and ζ_{0} the maximum number of cut-vertices can be contained in one block (a maximal 2-connected subgraph) of G. It is known that [Formula presented]. Let A be the class of k-γ_{c}-critical graphs containing a block B_{0} which has [Formula presented] cut-vertices. Further, for integer 0≤i≤2, we let A_{i} be the subclass of A such that k≡i(mod3). In this paper, we show that ζ≤{ζ_{0}+2ifG∈A_{0},ζ_{0}ifG∈A_{1},ζ_{0}+1ifG∈A_{2}.Further, we characterize all graphs in the classes A_{i} whose number of cut-vertices achieve the upper bound for each i∈{0,1,2}.

Original language | English |
---|---|

Article number | 126248 |

Journal | Applied Mathematics and Computation |

Volume | 406 |

DOIs | |

Publication status | Published - 1 Oct 2021 |

## Keywords

- Connected domination

## ASJC Scopus subject areas

- Computational Mathematics
- Applied Mathematics