Degree-constrained spanning tree: Difference between revisions

Revision as of 05:40, 28 January 2025

Revision as of 05:46, 28 January 2025

Line 1:

[[File:Degree-constrained spanning tree.png|thumb|350px|On the left, a spanning tree can be constructed where allthe verticesvertex havewith the highest [[Degree (graph theory)|degree]] is 2 or(thus, lessa max degree 2 tree).</br> On the right, the central vertex must have degree at least 5 in any tree spanning this graph, so a 2 degree constrained tree cannot be constructed here.]]

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