1. Complementary Graphs with Flows Less Than Three
- Author
-
Meiling Wang, Xueliang Li, and Jiaao Li
- Subjects
Discrete mathematics ,Simple graph ,Conjecture ,Closure operation ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Graph ,Theoretical Computer Science ,Combinatorics ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,05C21, 05C40, 05C07 ,Mathematics - Abstract
X. Hou, H.-J. Lai, P. Li and C.-Q. Zhang [J. Graph Theory 69 (2012) 464-470] showed that for a simple graph $G$ with $|V(G)|\ge 44$, if $\min\{\delta(G),\delta(G^c)\}\ge 4$, then either $G$ or its complementary graph $G^c$ has a nowhere-zero $3$-flow. In this paper, we improve this result by showing that if $|V(G)|\ge 32$ and $\min\{\delta(G),\delta(G^c)\}\ge 4$, then either $G$ or $G^c$ has flow index strictly less than $3$. Our result is proved by a newly developed closure operation and contraction method., Comment: 16 pages, 4 figures
- Published
- 2019
- Full Text
- View/download PDF