A k-weak bisection of a cubic graph G is a partition of the vertex-set of G into two parts V 1 and V 2 of equal size, such that each connected component of the subgraph of G induced by V i (i = 1, 2) is a tree of at most k − 2 vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere-zero r-flow has a [r]-weak bisection. In this article, we study problems related to the existence of k-weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.

Flows and Bisections in Cubic Graphs

Mazzuoccolo, Giuseppe;
2017-01-01

Abstract

A k-weak bisection of a cubic graph G is a partition of the vertex-set of G into two parts V 1 and V 2 of equal size, such that each connected component of the subgraph of G induced by V i (i = 1, 2) is a tree of at most k − 2 vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere-zero r-flow has a [r]-weak bisection. In this article, we study problems related to the existence of k-weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.
2017
cubic graphs, circular nowhere-zero flows, bisections
File in questo prodotto:
File Dimensione Formato  
revision4.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Accesso ristretto
Dimensione 309.68 kB
Formato Adobe PDF
309.68 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/960862
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 11
social impact