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

Swiss Distance University of Applied Sciences
Nankai University
Private University for Health Sciences, Medical Informatics and Technology
Tampere University
City University of New York
Meta
Guizhou University of Finance and Economics
Teacher Training University
TU Wien
Aalto University
Peking University

Research output: Contribution to journal › Article › 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
Journal	Applied Mathematics and Computation
Volume	380
DOIs	https://doi.org/10.1016/j.amc.2020.125239
Publication status	Published - 1 Sept 2020
Externally published	Yes

Keywords

Data science
Graph measures
Graphs
Networks
Quantitative graph theory
Symmetry

Access to Document

10.1016/j.amc.2020.125239

Cite this

@article{871a8db2ea494aeaa79dd98c16a80267,

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",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

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.",

}

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 - https://www.scopus.com/pages/publications/85083681263

U2 - 10.1016/j.amc.2020.125239

DO - 10.1016/j.amc.2020.125239

M3 - Article

AN - SCOPUS:85083681263

SN - 0096-3003

VL - 380

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

M1 - 125239

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this