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

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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
Number of pages14
JournalApplied Mathematics and Computation
Volume380
DOIs
Publication statusPublished - 1 Sep 2020
MoE publication typeA1 Journal article-refereed

Keywords

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

Fingerprint 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