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

doi:10.1016/j.amc.2020.125239

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 journal › Article › Scientific › peer-review

Abstract

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

Original language	English
Article number	125239
Number of pages	14
Journal	Applied Mathematics and Computation
Volume	380
DOIs	https://doi.org/10.1016/j.amc.2020.125239
Publication status	Published - 1 Sep 2020
MoE publication type	A1 Journal article-refereed

Keywords

Data science
Graph measures
Graphs
Networks
Quantitative graph theory
Symmetry

Access to Document

10.1016/j.amc.2020.125239

Link to publication in Scopus

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

@article{e5cfed711c4e4a99ab17432274c9393a,

title = "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 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 δ.",

keywords = "Data science, Graph measures, Graphs, Networks, Quantitative graph theory, Symmetry",

author = "Matthias Dehmer and Frank Emmert-Streib and Abbe Mowshowitz and Aleksandar Ili{\'c} and Zengqiang Chen and Guihai Yu and Lihua Feng and Modjtaba Ghorbani and Kurt Varmuza and Jin Tao",

year = "2020",

month = sep,

day = "1",

doi = "10.1016/j.amc.2020.125239",

language = "English",

volume = "380",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

}

Relations and bounds for the zeros of graph polynomials using vertex orbits. / Dehmer, Matthias; Emmert-Streib, Frank; Mowshowitz, Abbe; Ilić, Aleksandar; Chen, Zengqiang; Yu, Guihai; Feng, Lihua; Ghorbani, Modjtaba; Varmuza, Kurt; Tao, Jin.

In: Applied Mathematics and Computation, Vol. 380, 125239, 01.09.2020.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

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

AU - Dehmer, Matthias

AU - Emmert-Streib, Frank

AU - Mowshowitz, Abbe

AU - Ilić, Aleksandar

AU - Chen, Zengqiang

AU - Yu, Guihai

AU - Feng, Lihua

AU - Ghorbani, Modjtaba

AU - Varmuza, Kurt

AU - Tao, Jin

PY - 2020/9/1

Y1 - 2020/9/1

N2 - 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 δ.

AB - 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 δ.

KW - Data science

KW - Graph measures

KW - Graphs

KW - Networks

KW - Quantitative graph theory

KW - Symmetry

UR - http://www.scopus.com/inward/record.url?scp=85083681263&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2020.125239

DO - 10.1016/j.amc.2020.125239

M3 - Article

AN - SCOPUS:85083681263

VL - 380

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

M1 - 125239

ER -