A note concerning some conjectures on cyclically 4-edge connected 3- regular graphs. (English) Zbl 0677.05054
Graph theory in memory of G. A. Dirac, Pap. Meet., Sandbjerg/Den. 1985, Ann. Discrete Math. 41, 171-177 (1989).
[For the entire collection see Zbl 0656.00008.]
Five conjectures about 1-edge connected graphs are considered and three of them are shown to be equivalent. For example, the conjecture that ‘Every cyclically 4-edge connected 3-regular graph G has a cyclic C such that G-V(C) is an independent set of vertices’ is shown to be equivalent to ‘Every 4-connected line graph is Hamiltonian’.
Five conjectures about 1-edge connected graphs are considered and three of them are shown to be equivalent. For example, the conjecture that ‘Every cyclically 4-edge connected 3-regular graph G has a cyclic C such that G-V(C) is an independent set of vertices’ is shown to be equivalent to ‘Every 4-connected line graph is Hamiltonian’.
Reviewer: C.R.J.Clapham
MSC:
| 05C40 | Connectivity |
