A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees (Q397062): Difference between revisions

In this paper, the authors focus on the existence of a spanning tree \(T\) of a connected simple graph \(G\), where all the vertices of a subset \(X\) of \(V(G)\) satisfy a special inequality concerning their degree \(d_T(x)\) in \(T\). More precisely, for a given mapping \(f\) from \(X\) to the set of integers, it is required that \(d_T (x)\geq f(x)\) for all \(x\in X\). In case \(X\) is an independent set, a necessary and sufficient condition for the existence of such a spanning tree is known from \textit{A. Frank} and \textit{A. Gyárfás} [Colloq. Math. Soc. János Bolyai 18, 353--364 (1978; Zbl 0389.05035)], and, independently, from \textit{A. Kaneko} and \textit{K. Yoshimoto} [Inf. Process. Lett. 73, No. 5--6, 163--165 (2000)]. The authors extend the result to the case where the subgraph \(G[X]\) of \(G\) induced by \(X\) has no induced path of order four, also showing that the condition is the best possible. This is done by exhibiting examples where \(G[X]\) has an induced path of order four but there exists no spanning tree fulfilling the inequality.