The complexity of spanning tree problems involving graphical indices

DOI10.1016/J.DAM.2024.01.005OpenAlexW4391018646WikidataQ129681732 ScholiaQ129681732MaRDI QIDQ6202942FDOQ6202942

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)

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

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

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)

Cites Work

• Graph theory
• Introduction to algorithms.
• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• Graph energy
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• Proof verification and the hardness of approximation problems
• 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
• Distance in graphs
• Topological index based on the ratios of geometrical and arithmetical means of end-vertex degrees of edges
• Title not available (Why is that?)
• A unified approach to the extremal trees for different indices
• Trees with maximum general Randić index
• Title not available (Why is that?)
• On the Balaban index of trees
• Unified extremal results of topological indices and spectral invariants of graphs
• On the extremal values of general degree-based graph entropies
• Character of graphs with extremal Balaban index
• Extremal vertex-degree function index for trees and unicyclic graphs with given independence number
• Extremal problems for graphical function-indices and \(f\)-weighted adjacency matrix

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)