Signed graphs with two negative edges

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, σ) \leq \min \{F(H,σ_H) : (H,σ_H) \in {\cal G}(G)\}$. We prove that $F(G,σ) \leq 6$ if $(G,σ)$ contains a bridge and $F(G,σ) \leq 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,σ) \leq 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,σ) \leq 6$. Furthermore, if Tutte's 5-Flow Conjecture is true, then $(G,σ)$ admits a nowhere-zero 6-flow endowed with some strong properties.

No reviews yet.

No comments yet.