Previous Page 2

Displaying 21 – 22 of 22

Showing per page

Extension of several sufficient conditions for Hamiltonian graphs

Ahmed Ainouche (2006)

Discussiones Mathematicae Graph Theory

Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph ( K r K K ) K , 1 ≤ r ≤ s ≤ t or the graph ( ( n + 1 ) / 2 ) K K ( n - 1 ) / 2 . It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph...

Currently displaying 21 – 22 of 22

Previous Page 2