On low bound of degree sequences of spanning trees inK-edge-connected graphs (Q4242971)

Let \(G= (V,E)\) be a connected graph. A \(d_k\)-tree \(T\) of \(G\) is a spanning tree satisfying \[ d_T(v)\leq \Biggl\lfloor{d_G(v)+ k-1\over k}\Biggr\rfloor+ \alpha \] for each vertex \(v\), where \(\lfloor\;\rfloor\) is a lower integer form and \(\alpha\) depends on \(k\). The paper studies the relation between the edge connectivity and the maximum degree of the spanning trees of a graph. As main result it is shown that any \(k\)-edge-connected graph has a \(d_k\)-tree, where \(\alpha= 1\) for \(k=2\), and \(\alpha=2\) otherwise.