Spanning star trees in regular graphs (Q1376073): Difference between revisions

Given a graph \(G\) with vertex set \(V\), and \(W\subseteq V\), let \(S(W)\) be the subgraph consisting of \(W\), all edges incident to at least one vertex of \(W\), and all vertices adjacent to a vertex in \(W\). If \(S(W)\) is a tree containing all the vertices of \(G\), it is called a spanning star tree of \(G\). It is shown that for every \(r\geq 3\), there exists \(n_0(r)\) such that for all \(n\geq n_0\), there are \(r\)-regular \(n\)-vertex graphs that have spanning star trees, and ones that do not. Furthermore, the problem of determining whether a given regular graph has a spanning star tree is shown to be NP-complete.