2
$\begingroup$

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?. enter image description here

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ranveer Singh Aug 12 '16 at 5:52
  • $\begingroup$ 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. $\endgroup$ – Ranveer Singh Aug 12 '16 at 6:53
  • $\begingroup$ Ops, there was a mistake with sign. Hopefully now it is better. $\endgroup$ – Fedor Petrov Aug 12 '16 at 9:59
  • $\begingroup$ 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. ? $\endgroup$ – Ranveer Singh Aug 17 '16 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.