Degree-preserving spanning trees in small-degree graphs
type: Item
instance of: scholarly article
title: Degree-preserving spanning trees in small-degree graphs
zbMATH Open document ID: 0965.05035
DOI: 10.1016/S0012-365X(00)00005-4
author: Peter Damaschke
published in: Discrete Mathematics
publication date: 2001-08-02T00:00:00Z
review text: The degree-preserving spanning tree problem is to find, in a given connected graph \(G= (V,E)\), a spanning tree \(T= (V,F)\) with maximum number of vertices of the kind that all edges of \(E\) incident with such vertices belong to \(F\). The corresponding decision problem is denoted by DPST. The paper shows that the DPST problem is NP-complete for (1) bipartite planar graphs in which each vertex has degree at most 5; (2) planar graphs in which each vertex has degree at most 4; and (3) planar graphs in which each vertex has degree at most 3. Moreover, the paper establishes relations of the DPST problem to the Steiner problem in graphs and the feedback vertex set problem.
reviewed by: Dietmar Cieslik
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1506817
zbMATH Keywords: spanning tree
zbMATH Keywords: planar graphs
zbMATH Keywords: Steiner problem
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00005-4
OpenAlex ID: W2058281654
Wikidata QID: Q127481587
Recommended article: Spanning trees and spanning Eulerian subgraphs with small degrees
Recommended article: Spanning trees with small degrees and few leaves
Recommended article: Diameter-preserving spanning trees in sparse weighted graphs
Recommended article: On the Directed Degree-Preserving Spanning Tree Problem
Recommended article: The degree-preserving spanning tree problem in strongly chordal and directed path graphs
Recommended article: Degree-bounded minimum spanning trees
Recommended article: Spanning trees with small diameters
Recommended article: Spanning trees and spanning closed walks with small degrees
Recommended article: Tree spanners of bounded degree graphs
Recommended article: Low-Degree Spanning Trees of Small Weight
description: scientific article; zbMATH DE number 1506817