We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Modular Orientations of Random and Quasi-Random Regular Graphs.
- Authors
ALON, NOGA; PRAŁAT, PAWEŁ
- Abstract
Extending an old conjecture of Tutte, Jaeger conjectured in 1988 that for any fixed integer p ≥ 1, the edges of any 4p-edge connected graph can be oriented so that the difference between the outdegree and the indegree of each vertex is divisible by 2p+1. It is known that it suffices to prove this conjecture for (4p+1)-regular, 4p-edge connected graphs. Here we show that there exists a finite p0 such that for every p > p0 the assertion of the conjecture holds for all (4p+1)-regular graphs that satisfy some mild quasi-random properties, namely, the absolute value of each of their non-trivial eigenvalues is at most c1p2/3 and the neighbourhood of each vertex contains at most c2p3/2 edges, where c1, c2 > 0 are two absolute constants. In particular, this implies that for p > p0 the assertion of the conjecture holds asymptotically almost surely for random (4p+1)-regular graphs.
- Subjects
RANDOM graphs; NATURAL numbers; GRAPH connectivity; TOPOLOGICAL degree; EIGENVALUES; MATHEMATICAL constants; MODULES (Algebra)
- Publication
Combinatorics, Probability & Computing, 2011, Vol 20, Issue 3, p321
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548310000544