MOST-VITAL EDGE OF A GRAPH WITH RESPECT TO SPANNING-TREES

Authors
RAO VVB
Citation
Vvb. Rao, MOST-VITAL EDGE OF A GRAPH WITH RESPECT TO SPANNING-TREES, IEEE transactions on reliability, 47(1), 1998, pp. 6-7
Citations number
2
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Software Graphycs Programming","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Software Graphycs Programming
Journal title
IEEE transactions on reliability → ACNP
ISSN journal
00189529
Volume
47
Issue
1
Year of publication
1998
Pages
6 - 7
Database
ISI
SICI code
0018-9529(1998)47:1<6:MEOAGW>2.0.ZU;2-9
Abstract
A most-vital edge of a connected graph with respect to spanning trees is an edge whose removal most reduces the number of spanning trees. Ts en et al (1984) proposed a solution to the problem, based on determini ng the adjoint of a matrix of order n (n = number of nodes of the grap h). This paper presents a solution based on determining the adjoint of Psi = A x A(t) (A = reduced incidence-matrix of the graph); the order of Psi is (n - 1). This procedure leads to a resistance-analog method to determine the vital edge of a graph with respect to the spanning t rees.