# Determinant of block graph

A block in a graph is a maximal connected subgraph that has no cut-vertex. A complete graph having $n$ nodes is denote by $K_n$. A block graph is a graph in which each block is a complete graph. For example in figure a block graph with blocks $K_2,K_2,K_3,K_4$ and $K_5$. What will be determinant of adjacency matrix corresponding a general block graph?.

At first, it does not depend only the sizes of blocks (compare two trees on 4 vertices). At second, there is a recurrence for this value $\det(G)$coming from the leaf-block $B_0$ with $m$ vertices and a cut-vertex $v$: $$\det(G)=(-1)^{m}(m-2)\det(G\setminus(B_0\setminus v))+(-1)^{m-1}(m-1)\det(G\setminus B_0).$$

Namely, if $B_0$ has vertices denoted by $1,\dots,m$, and vertex $m$ is a cut-vertex (so, this block $B_0$ corresponds to the northwest corner of the adjacency matrix), we may do the following.

0) if $m=2$, we get $\det(G)=-\det(G\setminus B_0)$ immediately.

1) Subtract first row from second, third,..., $m$-th rows.

2) Add second,third,..., $(m-1)$-th columns to the first column.

3) Subtract the first row divided by $(m-2)$ (assuming $m>2$) from the $m$-th row. Now the matrix has an upper-triangular block of size $(m-1)$ and the identity easily follows.

• Can you please tell me from which row/column you are expanding the determinant. I have few comments (1) I think first term on RHS will have (-1)^(m-2) instead of (-1)^(m-1). (2) Matrix will have an upper triangular after your 2) step, to me step 3) looks redundant. – Ranveer Singh Aug 12 '16 at 5:52
• Also, above identity seems incorrect. For example determinant of block graph having $K_5, K_3$ blocks is -10, where from above formula it come out to be 8. – Ranveer Singh Aug 12 '16 at 6:53
• Ops, there was a mistake with sign. Hopefully now it is better. – Fedor Petrov Aug 12 '16 at 9:59
• Thanks for answer. I need some more help, now I want to calculate inverse of its adjacency matrix. Of course it will depend upon ordering of vertices. But for a given ordering can we get some expression for it. ? – Ranveer Singh Aug 17 '16 at 15:47