Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach

Matthias Dehmer, Zengqiang Chen, Frank Emmert-Streib, Abbe Mowshowitz, Yongtang Shi, Shailesh Tripathi, Yusen Zhang

    Research output: Contribution to journalArticleScientificpeer-review

    8 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)19-28
    Number of pages10
    JournalInformation Sciences
    Volume471
    Early online date29 Aug 2018
    DOIs
    Publication statusPublished - 1 Jan 2019
    Publication typeA1 Journal article-refereed

    Keywords

    • Data science
    • Graphs
    • Networks
    • Quantitative graph theory
    • Structural branching

    Publication forum classification

    • Publication forum level 1

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Theoretical Computer Science
    • Computer Science Applications
    • Information Systems and Management
    • Artificial Intelligence

    Fingerprint

    Dive into the research topics of 'Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach'. Together they form a unique fingerprint.

    Cite this