Modular Orientations of Random and Quasi-Random Regular Graphs

DOI10.1017/S0963548310000544zbMath1226.05222MaRDI QIDQ2998847

Paweł Prałat, Noga Alon

Publication date: 11 May 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

conjecture of Tutte

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

Random 4-regular graphs have 3-star decompositions asymptotically almost surely ⋮ On star decompositions of random regular graphs ⋮ Mod $(2p+1)$-Orientation on Bipartite Graphs and Complementary Graphs ⋮ Nowhere-zero 3-flows and modulo \(k\)-orientations

Cites Work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• On mod \((2p+1)\)-orientations of graphs
• Explicit construction of linear sized tolerant networks
• Eigenvalues and expanders
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Additive bases of vector spaces over prime fields
• On the second eigenvalue of a graph
• Nowhere-zero 3-flows of highly connected graphs
• Nowhere-zero flows in random graphs
• On the degrees of the vertices of a directed graph
• Expander graphs and their applications
• On the algebraic theory of graph colorings
• MaxCut in ${\bm H)$-Free Graphs

This page was built for publication: Modular Orientations of Random and Quasi-Random Regular Graphs