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

T. Bohme, T. Bohme, Haitze J. Broersma, Hilde Tuinstra

Research output: Book/ReportReportProfessional

33 Downloads (Pure)

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 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 $n/2+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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages7
ISBN (Print)0169-2690
Publication statusPublished - 1998

Publication series

NameMemorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427
PublisherUniversiteit Twente

Keywords

  • MSC-05C35
  • MSC-05C38
  • IR-30611
  • EWI-3247
  • METIS-141252
  • MSC-05C45

Cite this

Bohme, T., Bohme, T., Broersma, H. J., & Tuinstra, H. (1998). A note on a conjecture concerning tree-partitioning 3-regular graphs. (Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427). Enschede: Universiteit Twente.
Bohme, T. ; Bohme, T. ; Broersma, Haitze J. ; Tuinstra, Hilde. / A note on a conjecture concerning tree-partitioning 3-regular graphs. Enschede : Universiteit Twente, 1998. 7 p. (Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427).
@book{bf5c90e03b1248ed8ae9df30e050a05b,
title = "A note on a conjecture concerning tree-partitioning 3-regular graphs",
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 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 $n/2+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.",
keywords = "MSC-05C35, MSC-05C38, IR-30611, EWI-3247, METIS-141252, MSC-05C45",
author = "T. Bohme and T. Bohme and Broersma, {Haitze J.} and Hilde Tuinstra",
note = "Imported from MEMORANDA",
year = "1998",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427",
publisher = "Universiteit Twente",

}

Bohme, T, Bohme, T, Broersma, HJ & Tuinstra, H 1998, A note on a conjecture concerning tree-partitioning 3-regular graphs. Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427, Universiteit Twente, Enschede.

A note on a conjecture concerning tree-partitioning 3-regular graphs. / Bohme, T.; Bohme, T.; Broersma, Haitze J.; Tuinstra, Hilde.

Enschede : Universiteit Twente, 1998. 7 p. (Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427).

Research output: Book/ReportReportProfessional

TY - BOOK

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

AU - Bohme, T.

AU - Bohme, T.

AU - Broersma, Haitze J.

AU - Tuinstra, Hilde

N1 - Imported from MEMORANDA

PY - 1998

Y1 - 1998

N2 - 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 $n/2+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.

AB - 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 $n/2+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.

KW - MSC-05C35

KW - MSC-05C38

KW - IR-30611

KW - EWI-3247

KW - METIS-141252

KW - MSC-05C45

M3 - Report

SN - 0169-2690

T3 - Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427

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

PB - Universiteit Twente

CY - Enschede

ER -

Bohme T, Bohme T, Broersma HJ, Tuinstra H. A note on a conjecture concerning tree-partitioning 3-regular graphs. Enschede: Universiteit Twente, 1998. 7 p. (Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427).