Spanning tree with many leaves in quadratic graph

2014 IJRSC – Volume 3 Issue 1


Rastogi, Akanksa*
MIET, Meerut, India (

Singhal, Vinay
MIET, Meerut, India (


Many problems arising in computer science can be viewed as a problem of, given a graph, finding a spanning tree that satisfies a specified property. Another large class of properties deals with the structure of the leaves of the spanning tree. Here, we wish to find a spanning tree with a Lower bound on maximum number of leaves (NP-complete problem). Applications of this problem include communications networks, circuit layout, and graph Theoretic problem. A polynomial algorithm for constructing full spanning trees for 4-regular (Quadratic) graph is presented. For a connected graph G let L(G) denote the maximum number of leaves in any spanning tree of G. We give a simple construction and a complete proof that if G is a connected quadratic graph on n vertices, then L (G) ≥ 2n/5 +2. The main idea is to count the number of “dead leaves” as the tree is being constructed.

Keywords: Maximum leaf spanning tree; 4-regular graph; Quadratic graph; NP-complete; regular graph; dead leaves



*Corresponding Author