Relations and bounds for the zeros of graph polynomials using vertex orbits

Abstract In this paper, we prove bounds for the unique, positive zero of O G ★ ( z ) : = 1 − O G ( z ) , where OG(z) is the so-called orbit polynomial [1]. The orbit polynomial is based on the multiplicity and cardinalities of the vertex orbits of a graph. In [1] , we have shown that the unique, positive zero δ ≤ 1 of O G ★ ( z ) can serve as a meaningful measure of graph symmetry. In this paper, we study special graph classes with a specified number of orbits and obtain bounds on the value of δ.