The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, i...The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, is essential. Effective implementation of these heuristics necessitates both the adaptation of existing graph invariants and the invention of novel ones, which continues to be a relevant challenge. Numerous current invariants are capable of distinguishing a significant number of graphs rapidly in real-time scenarios. In this study, we present an invariant tailored for tournaments, a specific class of directed graphs. Tournaments are particularly intriguing because the count of distinct tournaments for a given number of vertices aligns with that of undirected graphs of the same size. The introduced invariant evaluates all possible tournament subsets derived from the original digraph that share the identical arc set. For each subset tournament, standard rankings are computed and aggregated to produce the final vertex scores, which serve as the new invariant. Our analysis indicates that this newly proposed invariant diverges from the most straightforward tournament invariant, which typically assigns scores to each participant. Preliminary computational tests demonstrate that the minimal correlation between the sequences generated by these two invariants occurs at a vertex count of 15.展开更多
文摘The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, is essential. Effective implementation of these heuristics necessitates both the adaptation of existing graph invariants and the invention of novel ones, which continues to be a relevant challenge. Numerous current invariants are capable of distinguishing a significant number of graphs rapidly in real-time scenarios. In this study, we present an invariant tailored for tournaments, a specific class of directed graphs. Tournaments are particularly intriguing because the count of distinct tournaments for a given number of vertices aligns with that of undirected graphs of the same size. The introduced invariant evaluates all possible tournament subsets derived from the original digraph that share the identical arc set. For each subset tournament, standard rankings are computed and aggregated to produce the final vertex scores, which serve as the new invariant. Our analysis indicates that this newly proposed invariant diverges from the most straightforward tournament invariant, which typically assigns scores to each participant. Preliminary computational tests demonstrate that the minimal correlation between the sequences generated by these two invariants occurs at a vertex count of 15.
