Projects per year
Abstract
Research on the structural complexity of networks has produced many useful results in graph theory and applied disciplines such as engineering and data analysis. This paper is intended as a further contribution to this area of research. Here we focus on measures designed to compare graphs with respect to symmetry. We do this by means of a novel characteristic of a graph G, namely an 'orbit polynomial.' A typical term of this univariate polynomial is of the form cz^{n}, where c is the number of orbits of size n of the automorphism group of G. Subtracting the orbit polynomial from 1 results in another polynomial that has a unique positive root, which can serve as a relative measure of the symmetry of a graph. The magnitude of this root is indicative of symmetry and can thus be used to compare graphs with respect to that property. In what follows, we will prove several inequalities on the unique positive roots of orbit polynomials corresponding to different graphs, thus showing differences in symmetry. In addition, we present numerical results relating to several classes of graphs for the purpose of comparing the new symmetry measure with existing ones. Finally, it is applied to a set of isomers of the chemical compound adamantane C_{10}H_{16}. We believe that the measure can be quite useful for tackling applications in chemistry, bioinformatics, and structureoriented drug design.
Original language  English 

Article number  8972417 
Pages (fromto)  3610036112 
Number of pages  13 
Journal  IEEE Access 
Volume  8 
DOIs  
Publication status  Published  1 Jan 2020 
MoE publication type  A1 Journal articlerefereed 
Keywords
 Data science
 Graph measures
 Graphs
 Networks
 Quantitative graph theory
 Symmetry
Fingerprint
Dive into the research topics of 'The orbitpolynomial: A novel measure of symmetry in networks'. Together they form a unique fingerprint.Projects
 1 Finished

Threedimensional Acoustic Manipulation of Multiple Microobjects
Tao, J.
01/09/2018 → 31/08/2021
Project: Academy of Finland: Other research funding