Maximal trees with bounded maximum degree in a graph (Q1268112): Difference between revisions

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.