We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
An Efficient Restoration Method for the Faint Dot Matrix Images

Ao Zhu Peng Cao
Random Articles
Reseach Article

A Study on ‘Number of Spanning Trees’

by Adarsh Kumar Verma, Saurabh Sharma, Anuj Tiwari
journal cover thumbnail

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

Powered by PhDFocusTM