Spanning trees of bounded degree

MaRDI QIDQ5947942zbMATH OpenFDO

Authors Andrzej Czygrinow, Genghua Fan, Glenn H. Hurlbert, H. A. Kierstead, William T. Trotter

Publication date 11 December 2001

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/121942, http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r33.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Hamilton pathspanning tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

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\).

Recommendations

• Spanning trees with bounded degrees
• Bounded degree spanning trees (extended abstract)
• scientific article; zbMATH DE number 434863
• scientific article; zbMATH DE number 2157456
• Degree bounded spanning trees

Cited in

(28)

• Degree-bounded minimum spanning trees
• Trees through specified vertices
• Spanning trees with bounded degrees
• A note on matchings and spanning trees with bounded degrees
• Near-optimal bounded-degree spanning trees
• Spanning trees without adjacent vertices of degree 2
• On a spanning tree with specified leaves
• Spanning trees in dense directed graphs
• Spanning caterpillars having at most \(k\) leaves
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• scientific article; zbMATH DE number 434863 (Why is no real title available?)
• Spanning \(k\)-ended trees of bipartite graphs
• Independence trees and Hamilton cycles
• scientific article; zbMATH DE number 2157456 (Why is no real title available?)
• Generalized degree conditions for graphs with bounded independence number
• Spanning \(k\)-trees of bipartite graphs
• Spanning k-ended trees of 3-regular connected graphs
• scientific article; zbMATH DE number 5174840 (Why is no real title available?)
• Spanning Trees with Bounded Maximum Degrees of Graphs on Surfaces
• A sufficient condition for a graph to have a k-tree
• Some results on spanning trees
• Degree bounded spanning trees
• The number of bounded‐degree spanning trees
• Spanning trees: A survey
• Spanning \(k\)-trees of \(n\)-connected graphs
• Spanning trees in graphs without large bipartite holes
• Spanning trees homeomorphic to a small tree
• On covering vertices of a graph by trees

This page was built for publication: Spanning trees of bounded degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5947942)