Hamiltonicity of connected domination critical graphs
Access Status
Fulltext not available
Authors
Kaemawichanurat, P.
Caccetta, Louis
Ananchuen, W.
Date
2018Type
Journal Article
Metadata
Show full item recordCitation
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
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.
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)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 set if G[D] is connected. The minimum cardinality of a ...