Add to ORKGA connected graph having large minimum vertex degree must have a spanning tree with many leaves. In particular, let l(n, k) be the maximum integer m such that every connected n-vertex graph with minimum degree at least k has a spanning tree with at least m leaves. Then l(n, 3) ≥ n/4 + 2, l(n, 4) ≥ (2n + 8) /5, and l(n, k) ≤ n − 3n/(k +1) + 2 for all k. The lower bounds are proved by an algorithm that constructs a spanning tree with at least the desired number of leaves. Finally, l(n, k) ≥ (1 − blnk/k)n for large k, again proved algorithmically, where b is any constant exceeding 2.5
Given n points in the plane, the degree-K span-ning tree problem asks for a spanning tree of min-imu...
: We consider the problem of constructing a spanning tree for a graph G = (V, E) with n vertices an...
We prove that any planar graph on n vertices has less than 5:2852n spanning trees. Under the restric...
We present two lower bounds for the maximum number of leaves in a spanning tree of a graph. For conn...
AbstractFor a connected simple graph G let L(G) denote the maximum number of leaves in any spanning ...
Abstract. For a connected graph G, letL(G) denote the maximum number of leaves in a spanning tree in...
We show that if G is a simple connected graph with |E(G)|≥|V(G)|+1/2t(t-1) and |V(G)|≠t+2, then G ha...
AbstractFor a connected simple graph G let L(G) denote the maximum number of leaves in any spanning ...
The preoblem of finding a spanning tree with maximum number of leaves is studied. A simple 2-approxi...
The preoblem of finding a spanning tree with maximum number of leaves is studied. A simple 2-approxi...
AbstractWe obtain a sufficient condition for K1,4-free graphs to have spanning trees with at most k ...
AbstractWe prove that the d-dimensional hypercube, Qd, with n = 2d vertices, contains a spanning tre...
This paper was written during the author’s Sabbatical visit at the University of Zimbabwe, Harare....
n 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph G with n ≥ 3 vertices, ...
AbstractLet T be a tree and m be a positive integer. The leaf degree of a vertex x∈V(G) is defined a...
Given n points in the plane, the degree-K span-ning tree problem asks for a spanning tree of min-imu...
: We consider the problem of constructing a spanning tree for a graph G = (V, E) with n vertices an...
We prove that any planar graph on n vertices has less than 5:2852n spanning trees. Under the restric...
We present two lower bounds for the maximum number of leaves in a spanning tree of a graph. For conn...
AbstractFor a connected simple graph G let L(G) denote the maximum number of leaves in any spanning ...
Abstract. For a connected graph G, letL(G) denote the maximum number of leaves in a spanning tree in...
We show that if G is a simple connected graph with |E(G)|≥|V(G)|+1/2t(t-1) and |V(G)|≠t+2, then G ha...
AbstractFor a connected simple graph G let L(G) denote the maximum number of leaves in any spanning ...
The preoblem of finding a spanning tree with maximum number of leaves is studied. A simple 2-approxi...
The preoblem of finding a spanning tree with maximum number of leaves is studied. A simple 2-approxi...
AbstractWe obtain a sufficient condition for K1,4-free graphs to have spanning trees with at most k ...
AbstractWe prove that the d-dimensional hypercube, Qd, with n = 2d vertices, contains a spanning tre...
This paper was written during the author’s Sabbatical visit at the University of Zimbabwe, Harare....
n 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph G with n ≥ 3 vertices, ...
AbstractLet T be a tree and m be a positive integer. The leaf degree of a vertex x∈V(G) is defined a...
Given n points in the plane, the degree-K span-ning tree problem asks for a spanning tree of min-imu...
: We consider the problem of constructing a spanning tree for a graph G = (V, E) with n vertices an...
We prove that any planar graph on n vertices has less than 5:2852n spanning trees. Under the restric...