Linear Algorithms for the Hosoya Index and Hosoya Matrix of a Tree

Aleksander Vesel
Additional contact information
Aleksander Vesel: Faculty of Natural Sciences and Mathematics, University of Maribor, SI-2000 Maribor, Slovenia

Mathematics, 2021, vol. 9, issue 2, 1-11

Abstract: The Hosoya index of a graph is defined as the total number of its independent edge sets. This index is an important example of topological indices, a molecular-graph based structure descriptor that is of significant interest in combinatorial chemistry. The Hosoya index inspires the introduction of a matrix associated with a molecular acyclic graph called the Hosoya matrix. We propose a simple linear-time algorithm, which does not require pre-processing, to compute the Hosoya index of an arbitrary tree. A similar approach allows us to show that the Hosoya matrix can be computed in constant time per entry of the matrix.

Keywords: Hosoya index; Hosoya matrix; optimal algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/2/142/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/2/142/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:2:p:142-:d:478074

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().