2016/04/27 by Edita Rollová, Rollová, Edita, Michael Schubert +3 · 1 citation
Engineering · Mathematics · #Advancements in Battery Materials #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1604.08053
arxiv created 2016/04/27 · openalex publication_date 2016/04/27 · arxiv updated 2016/04/28 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The presented paper studies the flow number F(G,σ) of flow-admissible signed graphs (G,σ) with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph (G,σ) there is a set \cal G(G,σ) of cubic graphs such that F(G, σ) ≤ min \F(H,σH) : (H,σH) ∈ \cal G(G)\. We prove that F(G,σ) ≤ 6 if (G,σ) contains a bridge and F(G,σ) ≤ 7 in general. We prove better bounds, if there is an element (H,σH) of \cal G(G,σ) which satisfies some additional conditions. In particular, if H is bipartite, then F(G,σ) ≤ 4 and the bound is tight. If H is 3-edge-colorable or critical or if it has a sufficient cyclic edge-connectivity, then F(G,σ) ≤ 6. Furthermore, if Tutte's 5-Flow Conjecture is true, then (G,σ) admits a nowhere-zero 6-flow endowed with some strong properties.