The determinant of a unicyclic graph's neighborhood matrix

摘要

Let G be a unicyclic graph with n vertices and the unique cycle C, A(G) and N(G) its adjacency matrix and neighborhood matrix, respectively, and cl a scalar. We obtain an algorithm for computing the determinant of alphaI(n) + A(G) which uses O(n) space and O(n) arithmetic operations for delta less than or equal to rootn, where delta = min{d(G)(x) : x epsilon V(C)}. Applications include computing the determinants of A (G) and N(G), and computing the characteristic polynomial of A (G). (C) 2004 Elsevier Inc. All rights reserved.