Hamiltonicity of connected domination critical graphs
Citation
Kaemawichanurat, P. and Caccetta, L. and Ananchuen, W. 2018. Hamiltonicity of connected domination critical graphs. Ars Combinatoria. 136: pp. 127-151.
Source Title
Ars Combinatoria
ISSN
School
School of Electrical Engineering, Computing and Mathematical Science (EECMS)
Collection
Abstract
© 2018 Charles Babbage Research Centre. All rights reserved. A graph G is said to be k-yc-critical 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 l-connected k-yc-critical graphs are Hamiltonian. In this paper, for I > 2, we prove that if k - 1,2 or 3, then every l-connected k-yc-critical graph is Hamiltonian. We further show that, for n > (k - 1)k + 3, the class of i-connected Jt-yc-critical non-Hamiltonian graphs of order n is empty if and only if k = 1,2 or 3.
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 k-extendable 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-γc-critical 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 ...