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) < ...

Ananchuen, N.; Ananchuen, W.; Caccetta, Louis (2017)A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set ...