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

Share/Save/Bookmark

Bohme, T. and Broersma, Hajo and Tuinstra, Hilde (1998) A note on a conjecture concerning tree-partitioning 3-regular graphs. [Report]

[img]
Preview
PDF
116Kb
Abstract: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 �rst 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
12
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
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/30611
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141252