The complexity of spanning tree problems involving graphical indices

Yanni Dong, Hajo Broersma, Yuhang Bai, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We consider the computational complexity of spanning tree problems involving the graphical function-index. This index was recently introduced by Li and Peng as a unification of a long list of chemical and topological indices. We present a number of unified approaches to determine the NP-completeness and APX-completeness of maximum and minimum spanning tree problems involving this index. We give many examples of well-studied topological indices for which the associated complexity questions are covered by our results.

Original languageEnglish
Pages (from-to)143-154
Number of pages12
JournalDiscrete Applied Mathematics
Volume347
DOIs
StatePublished - 15 Apr 2024

Keywords

  • APX-complete
  • Graphical function-index
  • NP-complete
  • Spanning tree

Fingerprint

Dive into the research topics of 'The complexity of spanning tree problems involving graphical indices'. Together they form a unique fingerprint.

Cite this