BFS-Lex Coordinate System & Neighborhood Definitions
A rigorous coordinate system and structural partitioning model for resolving out-degree distributions and evaluating the Second Neighborhood Conjecture (SSNC).
BFS-Lex & Triangles
Well-ordering, rooted distance layers $R_i$, and transitive triangles.
Forward & Back Partitions
Interior, exterior, connected back, and disconnected back sets.
Minimum Counterexample
MCE conditions and optimization over induced subgraphs $G_k$.
BFS-Lex Coordinate System & Transitive Triangles
For any finite, connected oriented graph $G \in \mathcal{O}$ and root vertex $v_0 \in V(G)$, there exists a unique Well-Ordering of $V(G)$ induced by a breadth-first search (BFS) algorithm combined with a lexicographical tie-breaking rule.
Transitive Triangle Definition
A triple of vertices $x, y, u$ in an oriented graph $G$ forms a transitive triangle if:
This triple induces an acyclic orientation of a 3-cycle in the graph structure.
Interior & Exterior Neighbors
Let $u_i \in R_i$ be a parent node in the rooted layering, and let $v_{i+1} \in R_{i+1}$ be one of its children.
Interior Neighbors
label: int_nbrThe interior neighbors of $v_{i+1}$ with respect to $u_i$ are:
The interior degree of $v_{i+1}$ with respect to $u_i$ is $|\text{int}(u_i, v_{i+1})|$.
Exterior Neighbors
label: ext_nbrThe exterior neighbors of $v_{i+1}$ with respect to $u_i$ are:
The exterior degree of $v_{i+1}$ with respect to $u_i$ is $|\text{ext}(u_i, v_{i+1})|$.
For the MDN $v_0$, all its out-neighbors are exterior neighbors because $R_0 = \{v_0\}$ and there are no earlier neighborhoods $R_{-1}$. Thus:
Back Neighbors & Layer Partitions
Let $v_0$ be the MDN, and let $u_i \to v_{i+1} \in G$, with $u_i \in R_i$ and $v_{i+1} \in R_{i+1}$. The set of back neighbors from $v_i$ is $\text{back}(v_j)$. The set of all back neighbors of $u_i$ is denoted:
Connected Back Neighbors
label: conn_back_defGiven parent-child arc $u \to v$ ($u \in R_i, v \in R_{i+1}$), an outgoing arc $u \to v \to w$ is classified as connected back neighbors if the target vertex $w$ resides in the immediately preceding adjacent layer ($R_i$).
Disconnected Back Neighbors
label: disc_back_defGiven parent-child arc $u \to v$ ($u \in R_i, v \in R_{i+1}$), an outgoing arc $u \to v \to w$ is classified as disconnected back neighbors if target $w$ resides in an earlier layer separated by at least one intermediate layer.
Visualizing Arc Classifications Across Rooted Layers
The Minimum Counterexample (MCE)
This minimum counterexample approach is formulated for analyzing the Second Neighborhood Conjecture (SSNC):
Let $G \in \mathcal{O}$ be an oriented graph. Let $\mathcal{C}$ be the (possibly empty) set of all counterexamples to SSNC. Let $G \in \mathcal{C}$ be a counterexample. Let $\omega$ be a BFS-Lex well-ordering of $G$ rooted at its minimum out-degree node $v_0$. For a fixed integer $k$, let $G_k$ denote the induced subgraph consisting of the first $k$ vertices of $G$ under $\omega$.
MCE Structural Conditions
The graph $G \in \mathcal{C}$ is a Minimum Counterexample (MCE) if it is constructed using the BFS-Lex algorithm rooted at a minimum out-degree node $v_0$ and which also minimizes:
- The interior neighbors $|\text{int}(u_i, v_{i+1})|$
- The maximum total interior degree in each layer across induced subgraphs $G_k$