Some remarks on Jaeger's dual-hamiltonian conjecture (Q1296151)

From MaRDI portal





scientific article; zbMATH DE number 1314952
Language Label Description Also known as
English
Some remarks on Jaeger's dual-hamiltonian conjecture
scientific article; zbMATH DE number 1314952

    Statements

    Some remarks on Jaeger's dual-hamiltonian conjecture (English)
    0 references
    0 references
    0 references
    12 July 1999
    0 references
    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.
    0 references
    cubic graph
    0 references
    dual-hamiltonian
    0 references
    hamiltonian cocircuit
    0 references
    partition
    0 references
    cycles
    0 references

    Identifiers