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

Computing Sciences

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

6 Citations (Scopus)

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
Publication type	A1 Journal article-refereed

Keywords

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

Access to Document

10.1016/j.amc.2020.125239

Cite this

@article{59a265568262445a8c406bd649df39d7,

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

}

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

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

Publication forum classification

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this