Page 75 - Textos de Matemática Vol. 39

ALGORITHM FOR K-MATCHINGS IN BIPARTITE GRAPHS 65 3. Hafnians
Let G = (V, E) be an undirected graph on m := #V vertices. Identify V with ⟨m⟩. Let A(G) = [aij ]mi,j=1 ∈ {0, 1}m×m be the incidence matrix of G, i.e. aij = 1 if and only if (i, j) ∈ E. Since we assume that G ia undirected and has no self-loops, A(G) is a symmetric (0, 1) matrix with a zero diagonal. Denote by Sm(T ) ⊃ Sm,0(T ) the set of symmetric matrices and the subset of symmetric matrices with zero diagonal respectively, whose nonzero entries are in the set T ⊆ R. Thus any A = [aij] ∈ Sm,0(R+) induces G(A) = (V (A),E(A)), where V(A)=⟨m⟩and(i,j)∈E(A)ifandonlyifaij >0.SuchanAinducesa weighted graph Gw(A), where the edge (i,j) ∈ E(A) has the weight aij > 0. Let M ∈ Mk(G(A)) be a k-matching in G(A). Then the weight of M in Gw(A) is given by (i,j)∈M aij.
Assume that m is even, i.e. m = 2n. It is well known that the number of perfect matchings in G is given by haf A(G), the hafnian of A(G). More general, the total weight of all weighted perfect matchings of Gw(A),A ∈ S2n,0(R+) is given by haf A, the hafnian of A.
Recall the definition of the hafnian of 2n × 2n real symmetric matrix A = [aij] ∈ R2n×2n. Let K2n be the complete graph on 2n vertices, and denote by M(K2n) the set of all perfect matches in K2n. Then α ∈ M(K2n) can be represented as α = {(i1,j1),(i2,j2),..,(in,jn)} with ik < jk for k = 1,.... Denote aα := nk=1 aikjk . Then haf A := α∈M(K2n) aα. Note that haf A does not depend on the diagonal entries of A. Hafnian of A is related to the pfaffian of the skew symmetric matrix B = [bij] ∈ R2n×2n, where bij = aij if i < j, the same way the permanent of C ∈ Rn×n is related to the determinant of C. Recall pfaf B = α∈M(K2n) sgn(α)bα, where sgn(α) is the signature of the
permutation α ∈ S2n given by α = 1 2 3 4 .. 2n. Furthermore
i1 j1 i2 j2 .. jn Let A ∈ Sm(R). Then
det B = (pfaf B)2.
hafkA:= hafA[α,α], k=1,...,⌊m⌋. α∈Q2k,m 2
For A ∈ Sm,0(R+) hafk A is the total weight of all weighted k-matchings in Gw(A). Let haf0(A) := 1. Then the weighted matching polynomial of Gw(A) is
2k
given by Φ(x,A) := ⌊m ⌋ haf A x . It is known that a nonconstant Φ(x,A),
k=0 k
A ∈ Sm,0(R+) has only real negative roots [6].
Theorem 3.1. Let A ∈ Sm,0(R+) and k ∈ ⟨⌊m⌋⟩. Let Ak ∈ S2m−2k,0(R+) be
2 the following 2 × 2 block matrix Ak := A 1m,m−2k
(3.1) hafk A = haf Ak . (m − 2k)!
. Then
1m−2k,m 0