Traceability of connected domination critical graphs

Michael A. Henning, Nawarat Ananchuen, Pawaton Kaemawichanurat

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


A dominating set in a graph G is a set S of vertices of G such that every vertex outside S is adjacent to a vertex in S. A connected dominating set in G is a dominating set S such that the subgraph G[S] induced by S is connected. The connected domination number of G, γc(G), is the minimum cardinality of a connected dominating set of G. A graph G is said to be k-γc-critical if the connected domination number γc(G) is equal to k and γc(G+uv)<k for every pair of non-adjacent vertices u and v of G. Let ζ be the number of cut-vertices of G. It is known that if G is a k-γc-critical graph, then G has at most k−2 cut-vertices, that is, ζ≤k−2. In this paper, for k ≥ 4 and 0≤ζ≤k−2, we show that every k-γc-critical graph with ζ cut-vertices has a hamiltonian path if and only if k−3≤ζ≤k−2.

Original languageEnglish
Article number125455
JournalApplied Mathematics and Computation
Publication statusPublished - 1 Dec 2020


  • Connected domination critical
  • Domination
  • Hamiltonicity
  • Traceability

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Traceability of connected domination critical graphs'. Together they form a unique fingerprint.

Cite this