For some time the Petersen graph has been the only known Snark with circular flow number 5 (or more, as long as the assertion of Tutte’s 5-flow Conjecture is in doubt). Although infinitely many such snarks were presented eight years ago in [9], the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. We start this article with an analysis of sets of flow values, which can be transferred through flow networks with the flow on each edge restricted to the open interval (1,4) modulo 5. All these sets are symmetric unions of open integer intervals in the ring ℝ/5ℤ. We use the results to design an arsenal of methods for constructing snarks S with circular flow number ϕc(S)≥5. As one indication to the diversity and density of the obtained family of graphs, we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete.
The structure of graphs with circular flow number 5 or more, and the complexity of their recognition problem
Mazzuoccolo, Giuseppe;
2016-01-01
Abstract
For some time the Petersen graph has been the only known Snark with circular flow number 5 (or more, as long as the assertion of Tutte’s 5-flow Conjecture is in doubt). Although infinitely many such snarks were presented eight years ago in [9], the variety of known methods to construct them and the structure of the obtained graphs were still rather limited. We start this article with an analysis of sets of flow values, which can be transferred through flow networks with the flow on each edge restricted to the open interval (1,4) modulo 5. All these sets are symmetric unions of open integer intervals in the ring ℝ/5ℤ. We use the results to design an arsenal of methods for constructing snarks S with circular flow number ϕc(S)≥5. As one indication to the diversity and density of the obtained family of graphs, we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete.File | Dimensione | Formato | |
---|---|---|---|
snarks_F-rev1.1.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
Accesso ristretto
Dimensione
330.99 kB
Formato
Adobe PDF
|
330.99 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.