2019/06/20 by Michael A. Henning, Henning, Michael A., Nawarat Ananchuen +3
Mathematics · #05C45 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C45 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1906.08727
26 pages
arxiv created 2019/06/20 · arxiv updated 2019/06/21
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.