On the domination number of Hamiltonian graphs with minimum degree six

摘要

Let G = (V, E) be a simple graph. A set D subset of V is a dominating set of G if every vertex of V - D is adjacent to a vertex of D. The domination number of G, denoted by gamma(G), is the mini mum cardinality of a dominating set of G. We prove that if G is a Hamiltonian graph of order n with mini mum degree at least six, then gamma(G) <= 6n/17. (C) Elsevier Ltd. All rights reserved.