Some remarks on Jaeger's dual-hamiltonian conjecture

Let \(G\) be a simple connected graph. Suppose that \(G\) contains two edge-disjoint circuits. Then \(G\) is said to be cyclically \(k\)-connected if whenever we partition \(G\) into two subgraphs \(H_1\) and \(H_2\) so that both contain circuits, we have \(| V(H_1)\cup V(H_2)| \geq k\). A cocircuit of \(G\) is a minimal set of edges of \(G\) whose removal disconnects \(G\). Thus \(H\) is cocircuit of \(G\) if and only if \(G - H\) has exactly two components and every edge of \(H\) is incident with both components. We say that \(H\) is a hamiltonian cocircuit if \(| H| = | E| - | V| + 2\) and that \(G\) is dual-hamiltonian if \(G\) has a hamiltonian cocircuit. The paper is concerned with a conjecture of \textit{F. Jaeger} [Proc. Fifth Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg (1974), 501-512], which suggest that every cyclically 4-connected cubic graph is dual-hamiltonian. The authors make several remarks to the conjecture and formulate three other conjectures that are proved to be equivalent to the Jaeger conjecture.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Some remarks on Jaeger's dual-hamiltonian conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296151)