has_strong_orientation_of_diameter_le
def
The simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices u, v is joined by a directed walk of length at most k; i.e. G has a strong orientation of directed diameter at most k (oriented diameter of G is at most k).
Statement
def has_strong_orientation_of_diameter_le {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
- Defined in
- arXiv:2610.09648 (An asymptotically tight bound on oriented diameter), Section 1: strong orientation and directed diameter; the oriented diameter is the minimum directed diameter over strong orientations.
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 2
- digraph_reach_withindigraph_reach_within D k u v: there is a directed walk of length at most k from u to v in the digraph D (equivalently, the directed…
- is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
- Used by 4
- cycle_graph_eight_strong_orientation_diameter_le_sevenSanity (non-vacuity): the 8-cycle, a bridgeless graph of diameter 4, has a strong orientation of directed diameter at most 7, namely the…
- oriented_diameter_bound_holds_monoIf every connected bridgeless graph of diameter d has a strong orientation of diameter at most k, the same holds for every k' >= k (f(d)…
- oriented_diameter_bound_holdsoriented_diameter_bound_holds d k: every finite connected bridgeless simple graph of diameter d (taken on vertex set Fin n, which loses…
- oriented_diameter_four_lower_boundf(4) >= 12: there is a finite connected bridgeless simple graph of diameter 4 that has no strong orientation of directed diameter at most…
Lean source view module on GitHub
def has_strong_orientation_of_diameter_le {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := ∃ D : Digraph V, is_graph_orientation G D ∧ ∀ u v, digraph_reach_within D k u v