TITLE: Determinant of block graph
QUESTION [2 upvotes]: 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?.

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 2, "question_id": 247281}