Available Online: 9 March 2014
Author/s:
Rastogi, Akanksa*
MIET, Meerut, India (Akanksharastogi.mca@gmail.com)
Singhal, Vinay
MIET, Meerut, India (Singhalmca04@gmail.com)
Abstract:
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
DOI: https://doi.org/10.5861/ijrsc.2014.603
Cite this article:
Rastogi, A., & Singhal, V. (2014). Spanning tree with many leaves in quadratic graph. International Journal of Research Studies in Computing, 3(1), 3-12. https://doi.org/10.5861/ijrsc.2014.603
*Corresponding Author