Maximal trees with bounded maximum degree in a graph

DOI10.1007/S003730050027MaRDI QIDQ1268112zbMATH OpenOpenAlexFDO

Authors Min Aung, Aung Kyaw

Publication date 14 October 1998

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s003730050027

zbMATH Keywords

spanning tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Review text

Let \(G\) be a graph with \(n\) vertices. \(d(v)\) denote the degree of the vertex \(v\). It is a native question to discuss the properties of a graph depending on its vertex degrees. For instance, it is well known that \(G\) is Hamiltonian if \(d(v)+ d(w)\geq n\) for any pair \(v\), \(w\) of non-adjacent vertices. Moreover, one of the authors showed, in former times, that if for any independent set of \(k\) vertices the sum of the vertex degrees is at least \(n-1\), then \(G\) has a spanning tree with maximum degree at most \(k\). The paper gives, in the first part, an overview of known results of such kind and reports facts of the size of largest trees with bounded degree. The main part discusses the strengthness of the results and considers all trees with bounded maximum degree which are maximal in \(G\). Finally, a generalization of a condition for Hamiltonicity is given.

Recommendations

• On the largest tree of given maximum degree in a connected graph
• scientific article; zbMATH DE number 5174840
• Maximum induced trees in graphs
• scientific article; zbMATH DE number 5811345
• scientific article; zbMATH DE number 932184
• On trees of bounded degree with maximal number of greatest independent sets
• The maximum degree in a random tree and related problems
• Maximum induced forests in graphs of bounded treewidth
• A note on trees of maximum weight and restricted degrees

Cited in

(16)

• A note on trees of maximum weight and restricted degrees
• Spanning spiders and light-splitting switches
• Vertex arboricity and maximum degree
• Maximum trees of finite sequences
• Number of vertices of degree three in spanning 3-trees in square graphs
• Closure and spanning trees with bounded total excess
• Maximum number of subtrees in cacti and block graphs
• Neighborhood unions and extremal spanning trees
• Two trees in maximal planar bipartite graphs
• Reducing the maximum degree of a graph by deleting vertices
• Spanning \(k\)-forests with large components in \(K_{1,k+1}\)-free graphs
• Reducing the maximum degree of a graph by deleting vertices: the extremal cases
• scientific article; zbMATH DE number 5174840 (Why is no real title available?)
• Maximal flow in branching trees and binary search trees
• Spanning trees: A survey
• Trees with maximum number of maximal matchings

This page was built for publication: Maximal trees with bounded maximum degree in a graph

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