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

Matthias Dehmer, Frank Emmert-Streib, Abbe Mowshowitz, Aleksandar Ilić, Zengqiang Chen, Guihai Yu, Lihua Feng, Modjtaba Ghorbani, Kurt Varmuza, Jin Tao

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)


In this paper, we prove bounds for the unique, positive zero of OG (z):=1−OG(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 OG (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 δ.

Original languageEnglish
Article number125239
JournalApplied Mathematics and Computation
Publication statusPublished - 1 Sept 2020
Publication typeA1 Journal article-refereed


  • Data science
  • Graph measures
  • Graphs
  • Networks
  • Quantitative graph theory
  • Symmetry

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Relations and bounds for the zeros of graph polynomials using vertex orbits'. Together they form a unique fingerprint.

Cite this