The complexity of spanning tree problems involving graphical indices

DOI10.1016/J.DAM.2024.01.005MaRDI QIDQ6202942zbMATH OpenOpenAlexWikidataFDO

Authors Yan-Ni Dong, Hajo Broersma, Yuhang Bai, Shenggui Zhang

Publication date 27 February 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.dam.2024.01.005

zbMATH Keywords

NP-completenessspanning treeAPX-completenessgraphical function-index

Mathematics Subject Classification ID

Trees (05C05) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Chemical graph theory (05C92)

Recommendations

• scientific article; zbMATH DE number 3980505
• Publication:4733693
• Complexity of spanning tree problems with leaf-dependent objectives
• Publication:4731019
• Complexity results for the spanning tree congestion problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2052088 (Why is no real title available?)
• scientific article; zbMATH DE number 2239310 (Why is no real title available?)
• A unified approach to the extremal trees for different indices
• Approximation algorithms for combinatorial problems
• Character of graphs with extremal Balaban index
• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• Distance in graphs
• Extremal problems for graphical function-indices and \(f\)-weighted adjacency matrix
• Extremal vertex-degree function index for trees and unicyclic graphs with given independence number
• Graph energy
• Graph theory
• Introduction to algorithms.
• Max-leaves spanning tree is APX-hard for cubic graphs
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• On the Balaban index of trees
• On the Estrada index conjecture
• On the extremal values of general degree-based graph entropies
• Optimization, approximation, and complexity classes
• Proof verification and the hardness of approximation problems
• Some APX-completeness results for cubic graphs
• The harmonic index for graphs
• Topological index based on the ratios of geometrical and arithmetical means of end-vertex degrees of edges
• Trees with maximum general Randić index
• Unified extremal results of topological indices and spectral invariants of graphs

Cited in

(1)

• Extremal results and bounds for atom-bond sum-connectivity index

This page was built for publication: The complexity of spanning tree problems involving graphical indices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202942)