On some conjectures on cubic 3-connected graphs (Q914697)

The authors reconsider certain properties of a special class of graphs. More specifically the graphs are cubic, 3-connected, finite, and loop- free, and the properties related to paths and can be formulated as the following three conjectures: 1) (Barnette) Every cubic 3-connected graphs is Hamiltonian. 2) (Jaeger) Every cubic cyclically 4-edge connected graph G has a cycle C such that G-V(C) is acyclic. 3) (Jackson, Fleisher) Every cubic cyclically 4-edge connected graph G has a cycle C such that V(G)-V(C) is an independent set of vertices. The authors show that these conjectures can be reformulated as the following three conjectures: 1') For every pair of edges belonging to the boundary of one given face of a cubic 3-connected bipartite planar graph, there exists a Hamilton cycle through these edges. 2') For every pair of non-adjacent edges of a cyclically 4-edge connected cubic graph G there exists a cycle C through these edges such that G-V(C) is acyclic. 3') For every pair of non-adjacent edges of a cyclically 4-edge connected cubic graph G there exists a cycle C through these edges such that V(G)- V(C) is an independent set of vertices. In addition to these refinements the authors present a number of auxiliary results most of them related to connectivity properties of graphs.