pith. sign in

arxiv: 1604.08053 · v1 · pith:WONGIOEUnew · submitted 2016-04-27 · 🧮 math.CO

Signed graphs with two negative edges

classification 🧮 math.CO
keywords sigmagraphsflowsignedthencubicedgesnegative
0
0 comments X
read the original abstract

The presented paper studies the flow number $F(G,\sigma)$ of flow-admissible signed graphs $(G,\sigma)$ with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph $(G,\sigma)$ there is a set ${\cal G}(G,\sigma)$ of cubic graphs such that $F(G, \sigma) \leq \min \{F(H,\sigma_H) : (H,\sigma_H) \in {\cal G}(G)\}$. We prove that $F(G,\sigma) \leq 6$ if $(G,\sigma)$ contains a bridge and $F(G,\sigma) \leq 7$ in general. We prove better bounds, if there is an element $(H,\sigma_H)$ of ${\cal G}(G,\sigma)$ which satisfies some additional conditions. In particular, if $H$ is bipartite, then $F(G,\sigma) \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,\sigma) \leq 6$. Furthermore, if Tutte's 5-Flow Conjecture is true, then $(G,\sigma)$ admits a nowhere-zero 6-flow endowed with some strong properties.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.