Two Sufficient Conditions for Hamilton and Dominating Cycles
Zh. G. Nikoghosyan · International Journal of Mathematics and Mathematical Sciences · 2012
We prove that if G is a 2-connect graph of size q the number of edges and minimum degree δ with δ ≥ 2q/3 /12-1/2, where 11 when δ 2 and 31 when δ ≥ 3, then each longest cycle in G 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 δ ≥ q 5/4 -1/2 is hamiltonian.Both results are sharp in all respects.We write G S for the subgraph of G induced by S. For a subgraph H of G, we use G\H short for G\V H .The neighborhood of a vertex x ∈ V G will be denoted by N x .Set d x |N x |.Furthermore, for a subgraph H of G and x ∈ V G , we define N H x N x ∩ V H and d H x|N H x |.A simple cycle or just a cycle C of length t is a sequence v 1 v 2 • • • v t v 1 of distinct vertices v 1 , . . ., v t with v i v i 1 ∈ E G for each i ∈ {1, . . ., t}, where v t 1 v 1 .When t 2, the cycle C v 1 v 2 v 1 on two vertices v 1 , v 2 coincides with the edge v 1 v 2 , and when t 1, the cycle C v 1 coincides with the vertex v 1 .So, all vertices and edges in a graph can be considered as cycles of lengths 1 and 2, respectively.Paths and cycles in a graph G are considered as subgraphs of G.If Q is a path or a cycle, then the length of Q, denoted by |Q|, is |E Q |.We write Q with a given orientation by Q.For x, y ∈ V Q , we denote by x Qy the subpath of Q in the chosen direction from x to y.For x ∈ V Q , we denote the hth successor and the hth predecessor of x on Q by x h and x -h , respectively.We abbreviate x 1 and x -1 by x and x -, respectively.