Article ID Journal Published Year Pages File Type
427816 Information Processing Letters 2011 4 Pages PDF
Abstract

Jaeger in 1984 conjectured that every (4p)(4p)-edge-connected graph has a mod (2p+1)(2p+1)-orientation. It has also been conjectured that every (4p+1)(4p+1)-edge-connected graph is mod (2p+1)(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)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)(2p+1)-orientation and δ(G)⩾4pδ(G)⩾4p, then L(G)L(G) also has a mod (2p+1)(2p+1)-orientation, which extends a result in Chen et al. (2001) [2].

► We study Mod (2p+1)(2p+1)-orientations in line graphs. ► Mod (2p+1)(2p+1)-contractible graphs are also discussed in this paper. ► We prove Jaegerʼs conjecture on line graphs would imply the truth on general graphs. ► If G∈M2p+1G∈M2p+1 with minimum degree at least 4, then L(G)∈M2p+1L(G)∈M2p+1.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,