Definitions
Definitions
This section serves as a quick reference to all the definitions I have outlined in my paper. Here, you'll find the foundational terms that will help you understand the proof and the data structure. I have also included a D3 visualization for each concept—just click to view and interact with the visualizations to deepen your understanding.
A directed graph \(G\) is called \textbf{oriented} if it has no self-loops (i.e., no arcs of the form \((u,u)\) where \(u\) is a node in \(G\)) and no symmetric arcs, that is, no arcs of the form \((u,v)\) and \((v,u)\) where \(u\) and \(v\) are nodes in \(G\).
Let \(G^2 = (V,E^2)\) where \(G=(V,E)\) is the original graph, and \(E^2\) is the set of arcs defined as:
\[E^2 = \{(u,v) \mid (u,v) \in E \text{ or } \exists w\in V \text{ such that } (u,w) \in E \text { and } (w,v) \in E\}\]
The \textbf{distance} between nodes \(u\) and \(v\), denoted \( \text{dist}(u,v) \), is the length of the shortest directed path from \(u\) to \(v\).
Let \(G = (V, E)\). The \textbf{first out-neighborhood} of a vertex \(v \in V\) is defined as:
\[
N^+(v) = \{w \in V \mid (v, w) \in E\}
\]
Let \(G = (V, E)\). The \textbf{second out-neighborhood} of a vertex \(v \in V\) is defined as:
\[
N^{++}(v) = \{u \in V \mid \exists w \in V \text{ such that } (v, w) \in E \text{ and } (w, u) \in E, \text{ and } u \notin N^+(v)\}
\]
Let \(G = (V, E)\). Let \(S \subseteq V\) be a subset of the vertices of G. Then the \textbf{induced subgraph} \(G[S]\) is the graph whose vertex set is \(S\) and whose edge set consists of all the edges in \(E\) that have both endpoints in \(S\).
\item An oriented graph $G \in \mathcal{O}$ is a \textbf{minimum counterexample} if it violates SSNC ($|N^{++}(u)| < |N^+(u)|$ for all $u$), but every $G'$ with $|E(G)| < |E(G')|$, $\exists u \in G' |N^{++}(u)| \ge |N^+(u)|$.
Let $G \in \mathcal{O}$ be an oriented graph and $u \in V(G)$. The node $u$ is a \textbf{Decreasing Neighborhood Sequence Property (DNSP)} node if its second out-neighborhood is strictly smaller than its first out-neighborhood:
$$|N^{++}(u)| < |N^+(u)|.$$
Let $u_i$ be a parent node, and let $v_{i+1}, w_{i+1} \in N^+(u_i)$ be distinct children of $u_i$. Suppose there exists a vertex $y_{i+2}$ such that $$ v_{i+1} \to y_{i+2} \in G \quad \text{and} \quad w_{i+1} \to y_{i+2} \in G, \text{but} u_i \not\to y_{i+2} \in G. $$ Then the quadruple $(u_i, v_{i+1}, w_{i+1}, y_{i+2})$ forms a \textbf{Seymour diamond}.
The \textbf{rooted neighborhood} at distance $i \ge 0$ from $v_0$ is the subgraph induced by the vertices at directed distance $i$ from $v_0$.
A triple of vertices $x,y,u$ in an oriented graph $G$ forms a \{transitive triangle\} if $$ x \to y,\qquad x \to u,\qquad y \to u, $$ i.e., the three vertices induce an acyclic orientation of a 3-cycle.
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.
The \textbf{interior neighbors} of $v_{i+1}$ with respect to $u_i$ are the vertices $$ \text{int}(u_i, v_{i+1}) = N^+(u_i) \cap N^+(v_{i+1}) \cap R_{i+1}. $$ The \textbf{interior degree} of $v_{i+1}$ with respect to $u_i$ is $$ |\text{int}(u_i, v_{i+1})|. \label{int_nbr} $$
Let $u_i \in R_i$ be a parent node, and let $v_{i+1}, w_{i+1} \in R_{i+1}$ be children of $u_i$. Then $v_{i+1}$ and $w_{i+1}$ are called \textbf{siblings}.
Let $u_i \in R_i$ be a parent of $v_{i+1} \in R_{i+1}$.
The \textbf{exterior neighbors} of $v_{i+1}$ with respect to $u_i$ are the vertices $$ \text{ext}(u_i,v_{i+1}) = N^{++}(u) \cap N^+(v_{i+1}) \cap R_{i+2}. $$
The \textbf{exterior degree} of $v_{i+1}$ with respect to $u_i$ is $$ |\text{ext}(u_i, v_{i+1})|.
Let $v_0$ be the MDN, and let $u_i \in R_i$ be a vertex in $G$ with an earlier neighbor $v_j \in R_j$. The set of \textbf{back arcs} from $u_i$ to $v_j$ is $\text{back}(u_i, v_{i+1})$. The set of all back arcs of $u_i$ is denoted $\bigcup_{j < i} R_j \text{back}(u_i)$.
Let $G = (V,E)$ be an oriented graph, and let $v_0 \in V$ be the vertex of minimum out-degree. A \textbf{Graph Level Order (GLOVER)} on $G$ consists of the following structure:
- \textbf{Leveled Rooted Neighborhoods}: Partition the vertices of $V$ into rooted neighborhoods $$R_i=\{v \in V : \text{dist}(v_0,v)=i\}, \text{ for } i=0,1,\dots,n.$$
- \textbf{Universal Level Order}: The rooted neighborhoods are well-ordered such that $R_i < R_j$ if and only if $i
- \textbf{Global Vertex Order}: For vertices $u \in R_i$ and $v \in R_j$ with $i
- \textbf{Principle of Optimality}: If a sequence of rooted neighborhoods $\{R_0, R_1, ..., R_k\}$ is an MCE environment, then for any $j > i$, the sub-sequence $\{R_i, ..., R_j\}$ must satisfy MCE conditions in its local coordinate subspace.
- \textbf{Global Vertex Order}: For vertices $u \in R_i$ and $v \in R_j$ with $i
An edge $e$ is \textbf{unnecessary} to the MCE $G$ if $G-\{e\}$ is still a counterexample to the conjecture.
\begin{definition}Let $G$ be an oriented graph represented by a Graph Level Order rooted at $v_0$. For vertices $v_k, w_k \in R_k$, define $v_k \sim w_k$ if there exists a rooted automorphism of $G$ fixing $v_0$ and preserving rooted neighborhoods $R_i$ such that $v_k \mapsto w_k$.\end{definition}
Let $u_k \in R_k, v_{k+1}, w_{k+1} \in R_{k+1}$.
Define $$T(u_k):=\{(v_{k+1},w_{k+1}) \in E | v_{k+1},w_{k+1} \in N^+(u_k),v_{k+1} \to w_{k+1}\}$$ denote the set of interior arcs among the children of $u_k$ in $R_{k+1}$.
Let $G \in \mathcal{O}$ be an oriented graph and $u \in V(G)$. The node $u$ is a \textbf{non-Seymour} vertex if its second out-neighborhood is strictly smaller than its first out-neighborhood:
$$|N^{++}(u)| < |N^+(u)|.$$
Let $G \in \mathcal{O}$ be an oriented graph and $u \in V(G)$. The node $u$ is a \textbf{Seymour} vertex if its second out-neighborhood at least as large as its first out-neighborhood:
$$|N^{++}(u)| \ge |N^+(u)|.$$
Note:
We’re continuously improving our visualizations to enhance your experience. Future updates will include additional visualizations, user interactions, and features like force-directed graphs. If you have feedback or suggestions, we’d love to hear from you! Stay tuned for updates.
We’re continuously improving our visualizations to enhance your experience. Future updates will include additional visualizations, user interactions, and features like force-directed graphs. If you have feedback or suggestions, we’d love to hear from you! Stay tuned for updates.