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