A note on a conjecture concerning tree-partitioning $3$-regular graphs

Rok, strany: 1999, 15 - 21

If $G$ is a $4$-connected maximal planar graph, then $G$ is hamiltonian (by a theorem of Whitney), implying that its dual graph $G^*$ is a cyclically $4$-edge connected $3$-regular planar graph admitting a partition of the vertex set into two parts, each inducing a tree in $G^*$, a so-called tree-partition. It is a natural question whether each cyclically $4$-edge connected $3$-regular graph admits such a tree-partition. This was conjectured by Jaeger, and recently independently by the first author. The main result of this note shows that each connected $3$-regular graph on $n$ vertices admits a partition of the vertex set into two sets such that precisely $((1) / (2)) n+2$ edges have end vertices in each set. This is a necessary condition for having a tree-partition. We also show that not all cyclically $3$-edge connected $3$-regular (planar) graphs admit a tree-partition, and present the smallest counterexamples.

ISO 690:

Böhme, T., Broersma, H., Tuinstra, H. 1999. A note on a conjecture concerning tree-partitioning $3$-regular graphs. In Tatra Mountains Mathematical Publications, vol. 18, no.4, pp. 15-21. 1210-3195.

APA:

Böhme, T., Broersma, H., Tuinstra, H. (1999). A note on a conjecture concerning tree-partitioning $3$-regular graphs. Tatra Mountains Mathematical Publications, 18(4), 15-21. 1210-3195.