Neighborhood unions and extremal spanning trees (Q2427493): Difference between revisions

Let \(V(G)\) (resp. \(E(G)\)) be the vertex (resp. the edge) set of a graph \(G\). The neighborhood \(N(X)\) of a set \(X\subset V(G)\) is defined to be the set of all vertices with at least one neighbor in \(X\). Let \(k\geq 1\) an integer. Define \(N_k(G)=\min_I| N(I)| \), where \(I\) ranges over sets of \(k\) independent vertices in \(G\). A spanning spider is a spanning tree with at most one branching vertex. Main results of the paper are - Let \(G\) be a connected graph with \(n\) vertices and let \(m\geq 2\) be an integer. If \(N_m(G)>\frac{m}{m+1}(n-m)\), then \(G\) has a spanning tree with at most \(m\) leaves. - Two sufficient conditions for the existence of a spanning spider centered at a prescribed vertex are given.