Spanning trees of bounded degree (Q5947942): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:58, 30 January 2024
scientific article; zbMATH DE number 1666862
Language | Label | Description | Also known as |
---|---|---|---|
English | Spanning trees of bounded degree |
scientific article; zbMATH DE number 1666862 |
Statements
Spanning trees of bounded degree (English)
0 references
11 December 2001
0 references
A classical theorem of Dirac says that a graph \(G= (V,E)\) with minimum degree at least \(|V|/2\) is Hamiltonian. As a corollary Ore showed that if the sum of the degrees of each pair of non-adjacent vertices is at least \(|V|-1\) then \(G\) has a Hamilton path. Such a path is just a spanning tree for \(G\) with small maximum degree. It is natural to ask to guarantee the existence of a spanning tree with a predetermined maximum degree \(k\). The paper discusses this question and gives a description of the structure of graphs satisfying \[ \sum_{v\in I} \text{degree}(v)\geq|V|-1 \] for every \(k\)-element independent set of vertices of \(G\).
0 references
Hamilton path
0 references
spanning tree
0 references