The complexity of spanning tree problems involving graphical indices
DOI10.1016/j.dam.2024.01.005OpenAlexW4391018646WikidataQ129681732 ScholiaQ129681732MaRDI QIDQ6202942
Hajo J. Broersma, Yuhang Bai, Sheng Gui Zhang, Yan-Ni Dong
Publication date: 27 February 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2024.01.005
Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Chemical graph theory (05C92)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of the maximum leaf spanning tree problem on planar and regular graphs
- Max-leaves spanning tree is APX-hard for cubic graphs
- The harmonic index for graphs
- Maxima and minima of the Hosoya index and the Merrifield-Simmons index
- On the Estrada index conjecture
- Topological index based on the ratios of geometrical and arithmetical means of end-vertex degrees of edges
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- Some APX-completeness results for cubic graphs
- Unified extremal results of topological indices and spectral invariants of graphs
- Extremal vertex-degree function index for trees and unicyclic graphs with given independence number
- On the extremal values of general degree-based graph entropies
- Graph Energy
- Proof verification and the hardness of approximation problems
- Distance in graphs
- Extremal Problems for Graphical Function-Indices and f-Weighted Adjacency Matrix
This page was built for publication: The complexity of spanning tree problems involving graphical indices
