Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs |
| |
Authors: | Moshe Rosenfeld |
| |
Institution: | (1) Department of Mathematics and Computer Science, Pacific Lutheran University, 98447 Tacoma, WA, USA |
| |
Abstract: | Summary A variety of examples of 4-connected 4-regular graphs with no pair of disjoint Hamiltonian circuits were constructed in response to Nash-Williams conjecture that every 4-connected 4-regular graph is Hamiltonian and also admits a pair of edge-disjoint Hamiltonian circuits. Nash-Williams's problem is especially interesting for planar graphs since 4-connected planar graphs are Hamiltonian. Examples of 4-connected 4-regular planar graphs in which every pair of Hamiltonian circuits have edges in common are included in the above mentioned examples.B. Grünbaum asked whether 5-connected planar graphs always admit a pair of disjoint Hamiltonian circuits. In this paper we introduce a technique that enables us to construct infinitely many examples of 5-connected planar graphs, 5-regular and non regular, in which every pair of Hamiltonian circuits have edges in common. |
| |
Keywords: | Primary 05C40 Secondary 05C45 |
本文献已被 SpringerLink 等数据库收录! |
|