Indian Journal of Mathematics Research

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Vertex Degree Preserving Spanning Trees in Graphs


Affiliations
1 Department of Mathematics and Computer Applications, PSG College of Technology, Coimbatore-641004, Tamil Nadu., India
     

   Subscribe/Renew Journal


A v-Degree Preserving Spanning Tree (v-DPST) of a graph G is defined as a spanning tree T of G such that degT(v) = degG(v). Results related to the existence, association with other existing special purpose spanning trees and count of such trees are presented in this paper. A suitable application of the defined tree is also explained.

Keywords

Spanning Trees, Distance Preserving Spanning Trees, Eccentricity Preserving Spanning Trees, Degree Constrained Spanning Trees, Matrix Tree Theorem, Multi-party Conference, Multicast
Subscription Login to verify subscription
User

Notifications
Font Size

  • Bocchi T, Gagliardi D and Lewinter M, Reach preserving properties of product graphs, Graph Theory Notes of New York 29 New York Academy of Sciences, pp 40-41, 1995.

  • Buckley F and Lewinter M, A note on graphs with diameter preserving spanning trees, Journal of Graph Theory, Vol.12,

  • Dean N, Kelman A K., Lih K W., Masseay W A and Winkler P, The spanning tree enumeration problem for digraphs, Graph Theory, Combinatorics and Algorithms, pp. 277-287, 1995.

  • Hanr L and Wang Y, A Novel Genetic Algorithm for Degree Constrained Minimum Spanning Tree Problem, International Journal of Computer Science and Network Security, Vol.6, No 7A, pp. 50-57, 2006. Issue 4, pp. 525 – 528, 1988.

  • Kirchhoff G, Uber die Auflosung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Strome gefuhrt wird, Ann. Phys. Chem. Vol.72, pp.497-508, 1847.

  • Lu H and Ravi R, The power of local optimization: approximation algorithms for maximum- leaf spanning tree. Technical Report CS-96-05, Brown University, 1996.

  • Mao L J, Deo N, Kumar N and Lang S D, A Comparison of Two Parallel Approximate Algorithms for DCMST problem, CONGRESSUS NUMERANTIUM, Vol. 123, pp. 15-32, 1997.

  • Mayeda W, Graph Theory, John Wiley, 1972.

  • Ore O, Theory of Graphs, Amer. Math. Soc. Publ., Providence 1962.

  • Pragyansmita Paul and Raghavan S V, Survey of Multicast Routing Algorithms and Protocols, Proceedings of the Fifteenth International Conference on Computer Communication (ICCC 2002), pp 902-926, 2002.

  • Ravi R, Sundaram R, Marathe M V, Rosenkrantz D J and Ravi S S, Spanning trees short and small, In Proceedings of the 5th Annual ACM- SIAM Symposium on Discrete Algorithms, pp. 546-555, 1994.

  • Yu P, Chebotarev and Shamis E V, The Matrix-Forest Theorem And Measuring Relations In Small Social Groups, Automation and Remote Control, Vol. 58, No. 9, pp.1505–1514, 1997.


Abstract Views: 449

PDF Views: 2




  • Vertex Degree Preserving Spanning Trees in Graphs

Abstract Views: 449  |  PDF Views: 2

Authors

R. Anitha
Department of Mathematics and Computer Applications, PSG College of Technology, Coimbatore-641004, Tamil Nadu., India
K. Sangavai
Department of Mathematics and Computer Applications, PSG College of Technology, Coimbatore-641004, Tamil Nadu., India

Abstract


A v-Degree Preserving Spanning Tree (v-DPST) of a graph G is defined as a spanning tree T of G such that degT(v) = degG(v). Results related to the existence, association with other existing special purpose spanning trees and count of such trees are presented in this paper. A suitable application of the defined tree is also explained.

Keywords


Spanning Trees, Distance Preserving Spanning Trees, Eccentricity Preserving Spanning Trees, Degree Constrained Spanning Trees, Matrix Tree Theorem, Multi-party Conference, Multicast

References