Hamiltonicity of connected domination critical graphs
Abstract
© 2018 Charles Babbage Research Centre. All rights reserved. A graph G is said to be kyccritical if the connected domination number yc(G) of G is k and yc(G + uv) < k for every uv ? E(G). The problem of interest for a positive integer I > 2 is to determine whether or not lconnected kyccritical graphs are Hamiltonian. In this paper, for I > 2, we prove that if k  1,2 or 3, then every lconnected kyccritical graph is Hamiltonian. We further show that, for n > (k  1)k + 3, the class of iconnected Jtyccritical nonHamiltonian graphs of order n is empty if and only if k = 1,2 or 3.
Citation
Kaemawichanurat, P. and Caccetta, L. and Ananchuen, W. 2018. Hamiltonicity of connected domination critical graphs. Ars Combinatoria. 136: pp. 127151.
Source Title
Ars Combinatoria
ISSN
School
School of Electrical Engineering, Computing and Mathematical Science (EECMS)
Collection
Related items
Showing items related by title, author, creator and subject.

Ananchuen, Nawarat (1994)Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n  1, G is said to be kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...

Kaemawichanurat, P.; Caccetta, Louis; Ananchuen, N. (2016)A graph G is said to be kγt critical if the total domination number γt(G)= k and γt (G + uv) < k for every uv /∈ E(G). A kγccritical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < ...

Kaemawichanurat, P.; Caccetta, Louis; Ananchuen, N. (2018)© Charles Babbage Research Centre. All rights reserved. A vertex subset D of G is a dominating set of G if every vertex in V(G)D is adjacent to a vertex in D. Moreover, a dominating set D of G is a connected dominating ...