%0 Journal Article
%T Two Sufficient Conditions for Hamilton and Dominating Cycles
%A Zh. G. Nikoghosyan
%J International Journal of Mathematics and Mathematical Sciences
%D 2012
%I Hindawi Publishing Corporation
%R 10.1155/2012/185346
%X We prove that if is a 2-connect graph of size (the number of edges) and minimum degree with , where when and when , then each longest cycle in is a dominating cycle. The exact analog of this theorem for Hamilton cycles follows easily from two known results according to Dirac and Nash-Williams: each graph with is hamiltonian. Both results are sharp in all respects. 1. Introduction Only finite undirected graphs without loops or multiple edges are considered. We reserve , , , and to denote the number of vertices (order), the number of edges (size), the minimum degree, and the connectivity of a graph, respectively. A graph is hamiltonian if contains a hamiltonian cycle, that is, a cycle of length . Further, a cycle in is called a dominating cycle if the vertices in are mutually nonadjacent. A good reference for any undefined terms is [1]. The following two well-known theorems provide two classic sufficient conditions for Hamilton and dominating cycles by linking the minimum degree and order . Theorem A (see [2]). Every graph with is hamiltonian. Theorem B (see [3]). If is a 2-connect graph with , then each longest cycle in is a dominating cycle. The exact analog of Theorem A that links the minimum degree and size easily follows from Theorem A and a particular result according to Nash-Williams [4] (see Theorem 1.1 below). Theorem 1.1. Every graph is hamiltonian if The hypothesis in Theorem 1.1 is equivalent to and cannot be relaxed to due to the graph consisting of two copies of and having exactly one vertex in common. Hence, Theorem 1.1 is best possible. The main goal of this paper is to prove the exact analog of Theorem B for dominating cycles based on another similar relation between and . Theorem 1.2. Let be a 2-connect graph with where when and when . Then each longest cycle in is a dominating cycle. To show that Theorem 1.2 is sharp, suppose first that , implying that the hypothesis in Theorem 1.2 is equivalent to . The graph shows that the connectivity condition in Theorem 1.2 cannot be relaxed by replacing it with . The graph with vertex set and edge set shows that the size bound cannot be relaxed by replacing it with . Finally, the graph shows that the conclusion ˇ°each longest cycle in is a dominating cycleˇ± cannot be strengthened by replacing it with ˇ° is hamiltonian.ˇ± Analogously, we can use , , and , respectively, to show that Theorem 1.2 is sharp when . So, Theorem 1.2 is best possible in all respects. To prove Theorems 1.1 and 1.2, we need two known results, the first of which is belongs Nash-Williams [4]. Theorem C (see [4]). If , then either
%U http://www.hindawi.com/journals/ijmms/2012/185346/