Zhang's Hamiltonian Weight Conjecture

Originator(s): Cun-Quan Zhang, West Virginia University

Conjecture/Question: Every 3-connected 3-regular graph having a Hamiltonian weight arises from K4 by a sequence of Delta-Wye operations.

Definitions/Background/motivation: A Hamiltonian weight on G is a map f from E(G) to {1,2} such that every family of cycles that covers each edge e exactly f(e) times consists of two Hamiltonian cycles. A Delta-Wye operation replaces a triangle in a 3-regular graph with a single vertex incident to the three edges that emanated from the triangle.

The study of Hamiltonian weights is motivated by the cycle double cover conjecture of Szekeres and Seymour and by the unique edge-3-coloring conjecture of Fiorini and Wilson.

Partial results: The conjecture was proved in [1] for those graphs not having the Petersen graph as a minor.

References:
[1] Lai, Hong-Jian; Zhang, Cun-Quan. Hamilton weights and Petersen minors. J. Graph Theory 38 (2001), no. 4, 197--219; MR2002g:05120 05C45 (05C70)

Keywords:

Back to Index Page Link to Glossary