## Abstract

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 language | English |
---|---|

Article number | 125455 |

Journal | Applied Mathematics and Computation |

Volume | 386 |

DOIs | |

Publication status | Published - 1 Dec 2020 |

## Keywords

- Connected domination critical
- Domination
- Hamiltonicity
- Traceability

## ASJC Scopus subject areas

- Computational Mathematics
- Applied Mathematics