A structural method for Hamiltonian graphs.
Gang Li, Bing Wei, Gao Tai-ping · 1995
In this paper, we shall introduce a special structure for graphs and show that a graph G is hamiltonian if and only if G has such a special structure. Using this result, we can prove a new weakened version of Fan's condition for hamiltonian graphs, which a recent result of Bedrossian, Chen and Schelp (1993). 1 Preliminaries and Main Results We consider only finite undirected graphs without loops or multiple edges. The set of vertices of G is denoted by V(G) or just by V; the set of edges by E(G) or just by E. We lise IGI a symbol for the cardinality of V(G). If Hand are subsets of V(G) or subgraphs of G, we denote by NH(S) the set of vertices in H which are adjacent to some vertex in S, and set dH(S) = IN H(S)I. If S ' = {u} and H G, then let NG(u) = N(u) and set dG(u) = d(u). For D ~ V(G), OlD) denotes the s~bgraph of G induced by D. For basic graph-theoretic terminology, we refer the