Neighborhood unions and extremal spanning trees (Q2427493)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Neighborhood unions and extremal spanning trees |
scientific article |
Statements
Neighborhood unions and extremal spanning trees (English)
0 references
13 May 2008
0 references
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.
0 references
spanning spider
0 references
spanning tree
0 references
neighborhood union
0 references
Hamilton path
0 references
traceable graph
0 references