Solution of the Hamiltonian problem for self-complementary graphs

AbstractA graph G is said to be highly constricted if there exists a nonempty subset S of vertices such that (i) G − S has more than |S| components, (ii) S induces the complete graph, and (iii) for every u ∈ S and v ∉ S, we have dG(u) > dG(v), where dG(u) denotes the degree of u in G. In this paper it is shown that a non-hamiltonian self-complementary graph G of order p is highly constricted, unless p = 4N and G is a particular graph G∗(4N). It is also proved that if G is a self-complementary graph of order p(≥8) and π its degree sequence, then G is pancyclic if π has a realization with a hamiltonian cycle, and G has a 2-factor if π has a realization with a 2-factor, unless p = 4N and G = G∗(4N)