Connected domination critical graphs with a block having maximum number of cut vertices

Michael A. Henning, Pawaton Kaemawichanurat

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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 B0 which has [Formula presented] cut-vertices. Further, for integer 0≤i≤2, we let Ai be the subclass of A such that k≡i(mod3). In this paper, we show that ζ≤{ζ0+2ifG∈A00ifG∈A10+1ifG∈A2.Further, we characterize all graphs in the classes Ai whose number of cut-vertices achieve the upper bound for each i∈{0,1,2}.

Original languageEnglish
Article number126248
JournalApplied Mathematics and Computation
Publication statusPublished - 1 Oct 2021


  • Connected domination

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Connected domination critical graphs with a block having maximum number of cut vertices'. Together they form a unique fingerprint.

Cite this