Signed graphs with two negative edges
Signed graphs with two negative edges
复制标题
DOI：
--
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Edita Rollov'a;Michael Schubert;E. Steffen
中科院分区：
文献类型：
--
作者：
Edita Rollov'a;Michael Schubert;E. Steffen
研究了具有两条负边的流容许符号图$（G，\sigma）$的流数F（G，\sigma）$.我们将我们的研究限制在三次图上，因为对于每个非三次符号图$（G，\sigma）$，存在一个三次图的集合${\cal G}（G，\sigma）$使得$F（G，\sigma）\leq \min \{F（H，\sigma_H）：（H，\sigma_H）\in {\cal G}（G）\}$。我们证明了$F（G，\sigma）\leq 6$如果$（G，\sigma）$包含一个桥和$F（G，\sigma）\leq 7$在一般情况下。我们证明了更好的界限，如果有一个元素$（H，\sigma_H）$${\cal G}（G，\sigma）$，满足一些额外的条件。特别地，如果$H$是二部的，则$F（G，\sigma）\leq 4$并且界是紧的。如果$H$是3-边可着色的或临界的，或者它有充分的循环边连通性，则$F（G，\sigma）\leq 6$。此外，如果Tutte的5-流猜想成立，则$（G，\sigma）$允许一个无处为零的6-流被赋予一些强性质。
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.