# Bounded degree spanning trees

A. Czumaj, W.-B. Strothmann, in: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97), 1997.

Conference Paper | Published | English
Author
Czumaj, Artur; Strothmann, Willy-Bernhard
Abstract
Given a connected graph \$G\$, let a \$dT\$-spanning tree of \$G\$ be a spanning tree of \$G\$ of maximum degree bounded by \$dT\$. It is well known that for each \$dT ge 2\$ the problem of deciding whether a connected graph has a \$dT\$-spanning tree is NP-complete. In this paper we investigate this problem when additionally connectivity and maximum degree of the graph are given. A complete characterization of this problem for 2- and 3-connected graphs, for planar graphs, and for \$dT=2\$ is provided. Our first result is that given a biconnected graph of maximum degree \$2dT-2\$, we can find its \$dT\$-spanning tree in time \$O(m+n^3/2)\$. For graphs of higher connectivity we design a polynomial-time algorithm that finds a \$dT\$-spanning tree in any \$k\$-connected graph of maximum degree \$k(dT-2)+2\$. On the other hand, we prove that deciding whether a \$k\$-connected graph of maximum degree \$k(dT-2)+3\$ has a \$dT\$-spanning tree is NP-complete, provided \$k le 3\$. For arbitrary \$k ge 3\$ we show that verifying whether a \$k\$-connected graph of maximum degree \$k(dT-1)\$ has a \$dT\$-spanning tree is NP-complete. In particular, we prove that the Hamiltonian path (cycle) problem is NP-complete for \$k\$-connected \$k\$-regular graphs, if \$k>2\$. This extends the well known result for \$k=3\$ and fully characterizes the case \$dT=2\$. For planar graphs it is NP-complete to decide whether a \$k\$-connected planar graph of maximum degree \$dG\$ has a \$dT\$-spanning tree for \$k=1\$ and \$dG > dT ge 2\$, for \$k=2\$ and \$dG > 2(dT-1) ge 2\$, and for \$k=3\$ and \$dG > dT = 2\$. On the other hand, we show how to find in polynomial (linear or almost linear) time a \$dT\$-spanning tree for all other parameters of \$k\$, \$dG\$, and \$dT\$.
Publishing Year
Proceedings Title
Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)
ISBN
ISSN
LibreCat-ID

### Cite this

Czumaj A, Strothmann W-B. Bounded degree spanning trees. In: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97). ; 1997. doi:10.1007/3-540-63397-9_9
Czumaj, A., & Strothmann, W.-B. (1997). Bounded degree spanning trees. Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97). https://doi.org/10.1007/3-540-63397-9_9
@inproceedings{Czumaj_Strothmann_1997, title={Bounded degree spanning trees}, DOI={10.1007/3-540-63397-9_9}, booktitle={Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97)}, author={Czumaj, Artur and Strothmann, Willy-Bernhard}, year={1997} }
Czumaj, Artur, and Willy-Bernhard Strothmann. “Bounded Degree Spanning Trees.” In Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97), 1997. https://doi.org/10.1007/3-540-63397-9_9.
A. Czumaj and W.-B. Strothmann, “Bounded degree spanning trees,” 1997, doi: 10.1007/3-540-63397-9_9.
Czumaj, Artur, and Willy-Bernhard Strothmann. “Bounded Degree Spanning Trees.” Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97), 1997, doi:10.1007/3-540-63397-9_9.

### Export

Marked Publications

Open Data LibreCat