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.
Reviewer: B.Zelinka

05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[1] G. A. Dirac, ?Some theorems on abstract graphs,? London Math. Soc., Ser. 3,2, 69-81 (1952). · Zbl 0047.17001
[2] O. Ore, ?Note on Hamilton circuits,? Am. Math. Mon.,67, 55 (1960). · Zbl 0089.39505
[3] L. Posa, ?A theorem concerning Hamilton lines,? Magyar Tud. Akad. Mat. Kutato Inst. Kozl.,7, 225-226 (1962). · Zbl 0114.40003
[4] J. A. Bondy, ?Properties of graphs with constraints on degrees,? Stud. Sci. Math. Hungar.,4, 473-475 (1969). · Zbl 0184.27702
[5] V. Chvatal, ?On Hamilton’s ideals,? J. Combinatorial Theory,12, 163-168 (1972). · Zbl 0213.50803
[6] M. Las Vergnas, ?Sur une propriété des arbres maximaux dans un graphe,? C.R. Acad. Sci., Paris,272, 12797-1300 (1971). · Zbl 0221.05053
[7] J. A. Bondy and V. Chvatal, ?A method in graph theory,? Discrete Math.,15, No. 2, 111-135 (1976). · Zbl 0331.05138
[8] F. Harary, Graph Theory, Addison-Wesley (1969).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.