B-partitions, application to determinant and permanent of graphs

2017/05/06 by Singh, Ranveer, Bapat, R. B.
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1705.02517

Abstract

Let G be a graph(directed or undirected) having k number of blocks. A B-partition of G is a partition into k vertex-disjoint subgraph (B₁,B₁,\hdots,B_k) such that B_i is induced subgraph of B_i for i=1,2,\hdots,k. The terms ∏_i=1^kdet(B_i), ∏_i=1^kper(B_i) are det-summands and per-summands, respectively, corresponding to the B-partition. The determinant and permanent of a graph having no loops on its cut-vertices is equal to summation of det-summands and per-summands, respectively, corresponding to all possible B-partitions. Thus, in this paper we calculate determinant and permanent of some graphs, which include block graph with negatives cliques, signed unicyclic graph, mix complete graph, negative mix complete graph, and star mix block graphs.

Related

• Algorithm for B-partitions, parameterized complexity of the matrix determinant and permanent
• Permanent of bipartite graphs in terms of determinants
• Destroying Non-Complete Regular Components in Graph Partitions
• A note on vertex partitions
• Canonical tree-decompositions of a graph that display its k-blocks