# zbMATH — the first resource for mathematics

Two theorems on Hamiltonian graphs. (English. Russian original) Zbl 0552.05038
Math. Notes 35, 32-35 (1984); translation from Mat. Zametki 35, No. 1, 55-61 (1984).
In the paper two conditions for the hamiltonicity of a graph are presented. The number of vertices of a graph G is denoted by p, the degree of a vertex x in G by $$d_ G(x)$$ and the set of vetices adjacent to x in G by $$N_ G(x)$$. Further $$\epsilon_ G(x)=\cup_{y\in N_ G(x)}N_ G(y)$$, $${\bar \epsilon}_ G(x)=\{y\in \epsilon_ G(x)| d_ G(y)\leq d_ G(x)\}$$. It is always supposed $$p\geq 3$$. A graph G has the property $$\xi$$, if it has no isolated vertices and for any vertex x of G the inequality $$d_ G(x)<(p-1)/2$$ implies $$| {\bar \epsilon}_ G(x)| <d_ G(x)$$ and the equality $$d_ G(x)=(p-1)/2)$$ implies $$| {\bar \epsilon}_ G(x)| \leq d_ G(x).$$ The p-closure $$C_ p(G)$$ of G is the (unique) graph H whose vertex set is equal to the vertex set of G, whose edge set contains the edge set of G as a subset, in which $$d_ H(x)+d_ H(y)<p$$ for any two non-adjacent vertices x, y holds and which has the minimum number of edges from all graphs with these properties. It is proved that if G or $$C_ p(G)$$ has the property $$\xi$$, then G is Hamiltonian.