Theorem: claw_free and paw_free sufficient for hamiltonian

math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/

GNU General Public License v3.0

15 stars 6 forks source link

Theorem: claw_free and paw_free sufficient for hamiltonian #513

Closed math1um closed 6 years ago

math1um commented 6 years ago

See: #512.

(1) Add property: is_claw_free_paw_free iff is_claw_free AND is_paw_free

(2) Add theorem goodman_hedetniemi(g) iff 2-connected AND is_claw_free_paw_free

This is a sufficient condition due to Goodman and Hedetniemi for a graph having a Hamilton cycle.

See: Goodman, S., and S. Hedetniemi. "Sufficient conditions for a graph to be hamiltonian." Journal of Combinatorial Theory, Series B 16.2 (1974): 175-180. (attached)

goodman-hedetniemi-sufficient-conditions-hamiltonicity-1974.pdf

yirkajk commented 6 years ago

Theorem 4 is: is 2-connected and claw free, paw free implies Hamiltonian