Minimum degree spanning tree

From formulasearchengine
Jump to navigation Jump to search

In graph theory, for a connected graph , a spanning tree is a subgraph of with the least number of edges that still spans . A number of properties can be proved about . is acyclic, has () edges where is the number of vertices in etc.

A minimum degree spanning tree is a spanning tree which has the least maximum degree. The vertex of maximum degree in is the least among all possible spanning trees of .

See Degree-Constrained Spanning Tree.

{{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }}