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

From MaRDI portal





scientific article; zbMATH DE number 1314952
Language Label Description Also known as
default for all languages
No label defined
    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