An Algorithmic Approach to Finding Degree-Doubling Nodes in Oriented Graphs

The Seymour Second Neighborhood Conjecture (SSNC) claims that there will always exist a node whose out-degree doubles in the square of an oriented graph. In this paper, we establish the Graph Level Order (GLOVER) data structure, which orders the nodes by shortest path from a minimum out-degree node and establishes a well-ordering of rooted neighborhoods. This data structure allows for the construction of decreasing sequences of subsets of nodes and allows us to partition transitive triangles into distinct sets. The decreasing sequence of nodes shows the non-existence of counterexamples to the SSNC and precisely identifies a path to the required node. Further, our algorithmic approach finds the occurrence of dense graphs inside the rooted neighborhoods. Beyond theoretical implications, the algorithm and data structure have practical applications in data science, network optimization and algorithm design.