Graphs with many strong orientations

DOI10.1137/15M1018885MaRDI QIDQ2813345zbMATH OpenFDO

Authors Paul Horn, Sinan Aksoy

Publication date 23 June 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.00767

zbMATH Keywords

Cheeger constantstrong orientationsstrongly connected

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Density (toughness, etc.) (05C42) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: We establish mild conditions under which a possibly irregular, sparse graph $G$ has "many" strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies a minimum degree condition of $(1+c_1)lo{g}_{2}n$ and has Cheeger constant at least $c_{2}fraclo{g}_{2}lo{g}_{2}nlo{g}_{2}n$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $lo{g}_{2}lo{g}_{2}n$ factor.

Recommendations

• Strongly 2-connected orientations of graphs
• Connectivities of random circulant digraphs
• Quasi-random oriented graphs
• Diameter of orientations of graphs with given minimum degree
• On the k-orientability of random graphs

Cites work

• A note on the isoperimetric constant
• A proof of Alon’s second eigenvalue conjecture and related problems
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Convexity in oriented matroids
• scientific article; zbMATH DE number 742958 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Robbins's Theorem for Mixed Multigraphs
• Size biased couplings and the spectral gap for random regular graphs
• Strongly connected orientations of mixed multigraphs
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• The isoperimetric number of random regular graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(2)

• On the Structure of the Strong Orientations of a Graph
• Minimum strong diameter of the strong product of complete multipartite graph and path

This page was built for publication: Graphs with many strong orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2813345)