Some remarks on Jaeger's dual-hamiltonian conjecture (Q1296151)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Some remarks on Jaeger's dual-hamiltonian conjecture |
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
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