首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Flow number and circular flow number of signed cubic graphs
Institution:Comenius University, Bratislava, Slovakia
Abstract:Let Φ(G,σ) and Φc(G,σ) denote the flow number and the circular flow number of a flow-admissible signed graph (G,σ), respectively. It is known that Φ(G)=?Φc(G)? for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that Φ(G,σ)?Φc(G,σ)<1 holds also for every flow-admissible signed graph (G,σ). This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory. For cubic graphs we show that Φ(G,σ)=3 if and only if Φc(G,σ)=3 and if Φ(G,σ){4,5}, then 4Φc(G,σ)Φ(G,σ). We also prove that all pairs of flow number and circular flow number that fulfil these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless signed cubic graphs. Finally, we prove that all currently known flow-admissible graphs without nowhere-zero 5-flow have flow number and circular flow number 6 and propose several conjectures in this area.
Keywords:Cubic graph  Signed graph  Flow number  Circular flow number
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号