Degree-constrained spanning tree: Difference between revisions

Revision as of 17:22, 28 August 2006

Revision as of 08:51, 25 September 2006

Line 3:

In [[graph theory]], a '''degree-constrained spanning tree''' is a [[spanning tree (mathematics)|spanning tree]] where the maximum vertex degree is limited to a certain constant ''k''. The '''degree-constrained spanning tree problem''' is to determine whether a particular graph has such a spanning tree for a particular ''k''. Formally:

Input: ''n''-node undirected graph G(V,E); positive integer ''k'' ≤≤ ''n''.

Question: Does G have a spanning tree in which no node has degree greater than ''k''?

This problem is [[NP-Complete]]. This can be shown by a reduction from the [[Hamiltonian path problem]]. It remains NP-complete even if ''k'' is fixed to a value ≥≥ 2 (in fact, for ''k''=2, this is the Hamiltonian path problem).

== References ==