Two theorems on Hamiltonian graphs

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.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: Two theorems on Hamiltonian graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800937)