Nowhere-zero flows on signed supereulerian graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908585113419776 |
|---|---|
| author | Wen, Chao Sun, Qiang Zhang, Chao |
| author_facet | Wen, Chao Sun, Qiang Zhang, Chao |
| contents | In 1983, Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow. We verify this conjecture for the class of flow-admissible signed graphs possessing a spanning even Eulerian subgraph, which includes as a special case all signed graphs with a balanced Hamiltonian circuit. Furthermore, we show that this result is sharp by citing a known infinite family of signed graphs with a balanced Hamiltonian circuit that do not admit a nowhere-zero 5-flow. Our proof relies on a construction that transforms signed graphs whose underlying graph admits a nowhere-zero 4-flow into a signed 3-edge-colorable cubic graph. This transformation has the crucial property of establishing a sign-preserving bijection between the bichromatic cycles of the resulting signed cubic graph and certain Eulerian subgraphs of the original signed graph. As an application of our main result, we also show that Bouchet's conjecture holds for all signed abelian Cayley graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_08192 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nowhere-zero flows on signed supereulerian graphs Wen, Chao Sun, Qiang Zhang, Chao Combinatorics In 1983, Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow. We verify this conjecture for the class of flow-admissible signed graphs possessing a spanning even Eulerian subgraph, which includes as a special case all signed graphs with a balanced Hamiltonian circuit. Furthermore, we show that this result is sharp by citing a known infinite family of signed graphs with a balanced Hamiltonian circuit that do not admit a nowhere-zero 5-flow. Our proof relies on a construction that transforms signed graphs whose underlying graph admits a nowhere-zero 4-flow into a signed 3-edge-colorable cubic graph. This transformation has the crucial property of establishing a sign-preserving bijection between the bichromatic cycles of the resulting signed cubic graph and certain Eulerian subgraphs of the original signed graph. As an application of our main result, we also show that Bouchet's conjecture holds for all signed abelian Cayley graphs. |
| title | Nowhere-zero flows on signed supereulerian graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.08192 |