Sufficient and Necessary Condition on Hamiltonian 3-Regular Plane Graph
XU Shou-chun · Zhongyang Minzu Daxue xuebao · 2008
In this paper,we proved Theorem 1 and its Corollary.Theorem 1 let g be a maximal planar graph,D(g) be a 3-regular plane graph and D(g) be dual of g,then the D(g) is Hamiltonian,if and only if,graph g has a t-t type of Gk,in other words,the graph g has 4-coloring C and the 4-coloring C has a dual bichromatic subgraph Gk=G_(αβ)∪G_(γδ),each of G_(αβ),G_(γδ) is a tree.Corollary let Ng be the number of t-t type Gk of all 4-colorings of maximal planar graph g,Nd be the number of Hamiltonian cycles of 3-reguale plane graph D(g) and D(g) be the dual of g,then Ng=Nd.An algorithm to generate all Hamiltonian cycles of 3-reguale plane graph is described.