Search

Let G be a connected graph on n vertices and D (G) be its distance matrix. The formula for computing the determinant of this matrix in terms of the number of vertices is known when the graph is either a tree or a unicyclic graph. In this work we generalize these results, obtaining the determinant of the distance matrix of any graph whose block decomposition consists of edges, unicyclic and bicyclic graphs. [ABSTRACT FROM AUTHOR]

Given a matrix, the Null Space Problem asks for a basis of its null space having the fewest nonzeros. This problem is known to be NP-complete and even hard to approximate. The null space of a forest is the null space of its adjacency matrix. Sander and Sander (2005) and Akbari et al. (2006), independently, proved that the null space of each forest admits a { − 1 , 0 , 1 } -basis. We devise an algorithm for determining a sparsest basis of the null space of any given forest which, in addition, is a { − 1 , 0 , 1 } -basis. Our algorithm is time-optimal in the sense that it takes time at most proportional to the number of nonzeros in any sparsest basis of the null space of the input forest. Moreover, we show that, given a forest F on n vertices, the set of those vertices x for which there is a vector in the null space of F that is nonzero at x and the number of nonzeros in any sparsest basis of the null space of F can be found in O ( n ) time. [ABSTRACT FROM AUTHOR]