Definitions

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 \(v_0\) be a minimum degree node, \(x\) be a node in \(G\), and \(y \in N^+(x)\) be in the container \(C_i\). A back arc is defined as an arc \((y,z)\) such that \(z \in N^+(y)\) and \(x \in C_j\), where \(j | < i\).

A Graph Level Order (GLOVER) on set \(S\) can be defined as follows:

• Leveled Structure: The elements of \( S \) are partitioned into levels of "containers" or "rankings," \( C_1, C_2, \dots, C_n \), where each container \( C_i \) forms a subset of \( S \) that maintains a total order. The containers themselves are ordered relative to each other, establishing a multi-level structure where all elements in \( C_i \) are ordered before those in \( C_{i+1} \).
• Non-triviality Requirement: At least one container \( C_i \) must contain more than one element, i.e., \( |C_i| > 1 \), to avoid trivial total orderings where all elements are isolated in singleton containers.
• Comparability within Containers: For any two elements \( u, v \in C_i \), their order is determined based on a specific criterion, such as a designated metric or property relevant to the application.
• Consistency Across Containers: For any two elements \( u \in C_i \) and \( w \in C_j \) with \( i < j \), \( u \) is considered less than \( w \). This enforces that the order of elements between containers aligns with the order of the containers themselves, establishing a coherent multi-level total order.
• Interior and Exterior Neighbors:
  1. If \( x, y \in C_i \) are nodes in the container \( C_i \), then they are considered interior neighbors.
  2. If \( x \in C_i \) and \( y \in C_j \) where \( i < j \), then \( y \) is an exterior neighbor of \( x \) if there is a connection between \( x \) and \( y \).

Let \(x \in G\) and \(y, u \in N^+(x)\) and \((y, u) \in G\). Then \(x\), \(y\), \(u\) form a transitive triangle.

Let \(x \in G\) and \(u_1, u_2 \in N^+(x)\). Then \(x\), \(u_1\), \(u_2\), \(y\) form a Seymour diamond if \((u_1, y)\) and \((u_2, y) \in G\).

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\).

In an oriented graph \(G = (V, E)\), a node \(v \in V\) is a \textbf{degree-doubling node} (or \textbf{Seymour vertex}) if \(|N^{++}(v)| \ge |N^+(v)|\), where \(N^+(v)\) and \(N^{++}(v)\) denote the first and second out-neighborhoods of \(v\) in \(G\), respectively.

Given an oriented graph \(G\) and a minimum out-degree node \(v_0\), a \textbf{rooted neighborhood} \(R_i\) of distance \(i\) is the subgraph of \(G\) induced by the set of all nodes at distance exactly \(i\) from \(v_0\). Formally, let \(V_i(v_0) = \{v \in V(G) \mid \text{dist}(v_0, v) = i\}\). Then, \[R_i = G[V_i(v_0)].\]

Let \((x,y), (x,u), (y,u) \in G\). Then \(x\), \(y\), and \(u\) form a \textbf{transitive triangle}, where \(x\) is a common predecessor of both \(y\) and \(u\), and \(y\) also connects to \(u\).

Let \(u_i\) be a node in the rooted neighborhood \(R_i\) for some \(i \geq 0\). A \textbf{child} of \(u_i\) is a node \(v_{i+1} \in R_{i+1}\) such that \((u_i, v_{i+1}) \in G\) (we also say that \(u_i\) is the \textbf{parent} of \(v_{i+1}\)).

Let \(u_i \in R_i\) be a parent node with children \(v_1, v_2 \in R_{i+1}\). We define the \textbf{interior neighbors of \(v_1\) with respect to \(u_i\)} as those nodes \(z \in V\) such that both \((u_i,z) \in E\) and \((v_1,z) \in E\). That is, nodes that are common out-neighbors of both \(u_i\) and \(v_1\), forming transitive triangles. \[ \text{int}(u_i, v_1):=N^+(u_i) \cap N^+(v_1) \] The \textbf{interior degree of \(v_1\) with respect to \(u_i\)}, denoted \(deg_{int}(u_i, v_1)\) is defined as: \[ deg_{\text{int}}(u_i, v_1):=|\text{int}(u_i, v_1)| \]

Let \(u_i \in R_i\) be the parent of \(v, w \in R_{i+1}\). Then \(v\) and \(w\) are said to be \textbf{siblings}.

Let \(u_i \in R_i\) be a parent of a node \(v_{i+1} \in R_{i+1}\). The \textbf{exterior neighbors of \(v_{i+1}\) with respect to \(u_i\)} are nodes \(z\) such that \(z\) is a second out-neighbor of \(u_i\) and a first out-neighbor of \(v_{i+1}\), i.e., \(z \in N^{++}(u_i) \cap N^+(v_{i+1})\). This implies that there exists a path \(u_i \rightarrow w \rightarrow z\), and an arc \(v_{i+1} \rightarrow z\) exists, but there is no direct arc \(u_i \rightarrow z\). Unlike the interior neighbors, exterior neighbors are neighbors of the child that are not shared by the parent. 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 a minimum out-degree node. Suppose that \(x\) is a node in the rooted neighborhood \(R_i\). A \textbf{back arc} is defined as an arc \((x, y)\) such that \(y \in N^+(x)\) and \(y \in R_j\), where \(j < i\).

A \textbf{Graph Level Order (GLOVER)} on a directed graph \(G = (V, E)\) can be defined as follows: \begin{enumerate} \item Leveled Rooted Neighborhood Structure: The vertices of \( V \) with minimum out-degree node \(v_0\) are partitioned into levels of Rooted Neighborhoods \( R_1, R_2, \ldots, R_n \), where \( R_i = \{v \in V : dist(v_0, v) = i\}\), and \(dist(v_0, v)\) is the shortest path from \(v_0\) to \(v\). \item Universal Rooted Neighborhood Order: The rooted neighborhoods are totally ordered such that \(R_i < R_j\) if and only if \(i < j\). \item Comparability Within Rooted Neighborhoods: For any two vertices \( u, v \in R_i \), their order is determined based on a specific metric (e.g., degree). \item Universal Vertex Order: For any two vertices \( u \in R_i \) and \( v \in R_j \) with \( i < j \), \( u \) is considered less than \( v \). \item Interior and Exterior Out-neighbors: For a node \(u \in R_i\) and \(v \in R_{i+1}\), where \(u\) is the parent of \(v\) \begin{itemize} \item The interior neighbors of \(u\) and \(v\) are defined by the set \(\text{int}(u, v)\). \item The exterior neighbors of \(u\) and \(v\) are defined by the set \(\text{ext}(u, v)\). \end{itemize} \end{enumerate}

For a node \(u \in G\) in an oriented graph \(G\), we say that \(u\) has the \textbf{Decreasing Neighborhood Sequence Property (DNSP)} if the size of its second out-neighbors is strictly smaller than the size of its first out-neighbors, i.e., \(|N^{++}(u)| < |N^+(u)|\).