A survey on orbit polynomials (Q6586307)

The orbit polynomial is a mathematical tool that leverages the cardinalities of vertex orbit sizes. It is defined as \( O_G(x) = \sum_n c x^n \), where \( c \) denotes the number of orbits of size \( n \) in the graph \( G \). Notably, all coefficients of the polynomial are positive.\N\NBy subtracting this polynomial from 1, the modified orbit polynomial is obtained: \( O^{\ast}_G(x) = 1 - O_G(x) \). This modified polynomial has a unique positive root, denoted by \( \delta \), which serves as a relative measure of the graph's symmetry. The value of \( \delta \) provides insights into the graph's symmetry level and allows for comparisons between graphs based on their symmetry properties.\N\NThis survey article presents results concerning orbit polynomials and automorphism groups of graphs. These findings highlight connections between the number of orbits and the structure of a graph's automorphism group, while also exploring the roots of orbit polynomials. Additionally, the article introduces a method for constructing graphs with prescribed orbit structures, providing a tool for generating graphs with a specific degree of symmetry.\N\NThe paper concludes with applications of the described concepts to real-world networks. Specifically, the results emphasize that Laplacian energy shows the strongest correlation with the symmetry measure \( \delta \). Additionally, the practical utility of \( \delta \) is demonstrated by calculating it for three molecular structures.