CFP last date
22 April 2024
Reseach Article

A Study on ‘Number of Spanning Trees’

by Adarsh Kumar Verma, Saurabh Sharma, Anuj Tiwari
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 73 - Number 19
Year of Publication: 2013
Authors: Adarsh Kumar Verma, Saurabh Sharma, Anuj Tiwari
10.5120/12994-0250

Adarsh Kumar Verma, Saurabh Sharma, Anuj Tiwari . A Study on ‘Number of Spanning Trees’. International Journal of Computer Applications. 73, 19 ( July 2013), 27-31. DOI=10.5120/12994-0250

@article{ 10.5120/12994-0250,
author = { Adarsh Kumar Verma, Saurabh Sharma, Anuj Tiwari },
title = { A Study on ‘Number of Spanning Trees’ },
journal = { International Journal of Computer Applications },
issue_date = { July 2013 },
volume = { 73 },
number = { 19 },
month = { July },
year = { 2013 },
issn = { 0975-8887 },
pages = { 27-31 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume73/number19/12994-0250/ },
doi = { 10.5120/12994-0250 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:40:32.536735+05:30
%A Adarsh Kumar Verma
%A Saurabh Sharma
%A Anuj Tiwari
%T A Study on ‘Number of Spanning Trees’
%J International Journal of Computer Applications
%@ 0975-8887
%V 73
%N 19
%P 27-31
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

There exist many algorithms for producing the spanning trees of a graph with better time and space complexities. In this research study, we are presenting a study on number of spanning trees and a technique based on the basic cycle to find the number of spanning trees and also the structure of all the spanning trees of a labeled and undirected graph.

References
  1. Char, J. P. , Generation of Trees, Two-Trees and Storage of Master Forests, IEEE Transactions on Circuit Theory, Vol. CT-15, pp. 128-138, 1968.
  2. Hakimi, S. L. , On Trees of a Graph and their Generation, Journal of the Franklin Institute, Vol. 272, No. 5, pp. 347-359, 1961.
  3. Kapoor, S. and H. Ramesh, Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs, SIAM Journal on Computing, Vol. 24, No. 2, 1995.
  4. Matsui, T. , An Algorithm for Finding All the Spanning Trees in Undirected Graphs, Technical Report: METR 93-08, Department of Mathematical Engineering and Information Physics, University of Tokyo, Tokyo, 1993.
  5. Mayeda, W. and S. Seshu, Generation of Trees without Duplications, IEEE Transactions on Circuit Theory, Vol. CT-12, pp. 181-185, 1965.
  6. Minty, G. J. , A Simple Algorithm for Listing All the Trees of a Graph, IEEE Transactions on Circuit Theory, Vol. CT-12, pp. 120, 1965.
  7. Sen Sarma, S. , A. Rakshit, R. K. Sen, and A. K. Choudhury, An Efficient Tree Generation Algorithm, Journal of the Institution of Electronics and Telecommunications Engineers, Vol. 27, No. 3, pp. 105-109, 1981.
  8. Shioura, A. and A. Tamura, Efficiently Scanning All Spanning Trees of an Undirected Graph, Research Report: B-270, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, 1993.
  9. Winter, P. , An Algorithm for the Enumeration of Spanning Trees, BIT, Vol. 26, pp. 44-62, 1986.
Index Terms

Computer Science
Information Sciences

Keywords

Basic cycle Internal edges External edges