Mod (2p 1)-orientations in line graphs

作者：Lai, Hong Jian; Li, Hao; Li, Ping; Liang, Yanting^*; Yao, Senmei

来源：Information Processing Letters, 2011, 111(23-24): 1085-1088.

DOI：10.1016/j.ipl.2011.09.005

• Combinatorial problems
• Nowhere zero flows
• Mod (2p 1)-orientation
• Mod (2p 1)-contractible
• Line graph

Jaeger in 1984 conjectured that every (4p)-edge-connected graph has a mod (2p 1)-orientation. It has also been conjectured that every (4p 1)-edge-connected graph is mod (2p 1)-contractible. In [Z.-H. Chen, H.-J. Lai, H. Lai, Nowhere zero flows in line graphs, Discrete Math. 230 (2001) 133-141], it has been proved that if G has a nowhere-zero 3-flow and the minimum degree of G is at least 4, then L(G) also has a nowhere-zero 3-flow. In this paper, we prove that the above conjectures on line graphs would imply the truth of the conjectures in general, and we also prove that if G has a mod (2p 1)-orientation and delta(G) >= 4p, then L(G) also has a mod (2p 1)-orientation, which extends a result in Chen et al. (2001) [2].

• 出版日期2011-12-15
• 单位新疆大学; 中国人民大学