Paper Info
Title
Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach.
Abstract
Structural properties of graphs and networks have been investigated across scientific disciplines ranging from mathematics to structural chemistry. Structural branching, cyclicity and, more generally, connectedness are well-known examples of such properties. In particular, various graph measures for detecting structural branching and cyclicity have been investigated. These measures are of limited applicability since their interpretation relies heavily on a certain definition of structural branching. In this paper we define a related measure, taking an approach to measurement similar to that of Lovász and Pelikán (On the eigenvalues of trees, Periodica Mathematica Hungarica, Vol. 3 (1–2), 1973, 175–182). We define a complex valued polynomial which also has a unique positive root. Analytical and numerical results demonstrate that this measure can be interpreted as a structural branching and cyclicity measure for graphs. Our results generalize the work of Lovász and Pelikán since the measure we introduce is not restricted to trees.
Year
DOI
Venue
2019
10.1016/j.ins.2018.08.043
Information Sciences
Keywords
Field
DocType
Quantitative graph theory,Networks,Structural branching,Graphs,Data science
Discrete mathematics,Graph,Social connectedness,Polynomial,Graph property,Eigenvalues and eigenvectors,Mathematics,Branching (version control)
Journal
Volume
ISSN
Citations 
471
0020-0255
0
PageRank 
References 
Authors
0.34
12
7
Name
Order
Citations
PageRank
Matthias Dehmer1863104.05
Zeng-Qiang Chen255072.38
Frank Emmert-streib350667.78
Abbe Mowshowitz4563124.43
Yongtang Shi551155.83
Shailesh Tripathi6225.50
Yusen Zhang792.93