Revista de Matema´tica: Teor´ıa y Aplicaciones 2002 9(2) : 51–58 cimpa – ucr – ccss issn: 1409-2433 the determinant of matching matrix in the evaluation of matching polynomial Shanaz A.Wahid∗ Received: 29 May 2001 Abstract A characterization is given for graphs whose matching polynomial is the deter- minant of their matching matrices. The matching matrix is then modified and its relation with other graph polynomials is examined. Keywords: Graphs, matching matrix, matching polynomial. Resumen Se da una caracterizaci’on de grafos cuyo polinomio de apareo es el determinante de sus matrices de apareo. La matriz de apareo es entonces modificada y se examina su relaci’on con otros polinomios de grafos. Palabras clave: Grafos, matriz de apareo, polinomio de apareo. Mathematics Subject Classification: 05A99 1 Introduction and basic definitions The graphs considered here will be finite, loopless and can have multiple edges unless otherwise stated. Let G be such a graph with p nodes and q edges. We define a matching M in G to be a spanning subgraph whose components are nodes and edges only. If M has k edges, then M is called a k-matching. Let us assign weights w1 and w2 to each node and edge respectively in G. w is the vector (w1, w2). If ak is the number of k-matchings in G, then the total weight of a k- matching is akw p−2k 1 w k 2 . The matching polynomial of G is M(G;w) = ∑[p/2] k=0 akw p−2k 1 w k 2 . An unwanted matching term is an expression of the form akw p−2k 1 w k 2 but does not cor- respond to a matching of G. U(G,w) is the sum of all such terms. This can arise in a ∗Centre for Combinatorics and Graph Theory Department of Mathematics and Computer Science, St. Augustine, The University of the West Indies. Trinidad and Tobago, West Indies. E-mail: shanazw@hotmail.com 51 52 s. wahid determinant expansion. The standard graph theoretical definitions are found in Harary [6]. Gv1, v2, . . . , , vn is the graph obtained from G by removing the set of nodes v1, v2, . . . , vn. Also G−e is the graph obtained form G by removing edge e.Sp is the symmetric group on p elements. The following definitions can be found in Farrell and Wahid [3]. The matching matrix of a labelled graph is the pxp matrix A(G) = (aij), where aij =  √ kw2 if ∃k edges between nodes vi and vj with i < j −√kw2 if ∃k edges between nodes vi and vj with i > j 0 if nodes vi and vj are not adjacent w1 if i = j A D-graph of G is a graph D(G) such that M(G,w) = |A(D(G))| . The d-function of G is the function defined on A(G) as follows: (i) If G is the null graph, then d(A(G)) = 1 (ii) d(A(G)) = |A(G)| ; if 0 < p ≤ 3. (iii) d(A(G)) = w1d/A(G − vi)) + w2 ∑ vivj∈E(G) d(A(G − vivj)), for p > 3. 2 Preliminary results The following result gives a reduction algorithm for finding M(G;w). Lemma 1 M(G;w) =M(G− eij ;w) + w2M(G− {vivj};w). Proof. This is proved by considering the matchings of G which do not have the edge eij or which must have the edge eij . The following result is the determinant expansion |A(G)| in terms of permutations. Lemma 2 |A(G)| = ∑σi∈Sp w(σi)e(σi) where w(σi) is the weight of the cycle σi and e(σi) = { 1 if σi is an even permutation −1 if σi is an odd permutation. Proof. This is straightforward. The following result is obtained by applying a function to the different sets of objects that are described by the principle of inclusion and exclusion. Lemma 3 f(T (1′, 2′, . . . , n′)) = f(T )− n∑ i=1 f(Ti) + n∑ i 6=j f(Ti,j)− . . .+ (−1)nf(T1,2,...,n) determinant of a matching matrix 53 Proof. Let bi for i = 1, 2, . . . , n be properties that are defined on the elements of a set. The principle of Inclusion and Exclusion states that N(b′1b ′ 2 · · · b′n) = N − n∑ i=1 N(bi) + n∑ i 6=j N(bibj)− . . .+ (−1)nN(b1b2 . . . bn). In using the principle of Inclusion and Exclusion we define a function f on each set of objects that are enumerated. T is the universal set with respect to the properties that are defined. The set whose elements have the properties bi and bj say is denoted by Ti,j and the set whose elements have none of the n properties bi for i = 1, 2, . . . , n is denoted by T (1′, 2′, . . . , k′). Thus f(Ti) = ∑ αi∈Ti f(αi). After applying f to the statement of the principle we get f(T (1′, 2′, . . . , n′)) = f(T )− n∑ i=1 f(ti) + n∑ i 6=j f(Ti,j)− . . .+ (−1)nf(T1,2,...,n). 3 The main results The following result gives |A(G)| in terms of matching terms and unwanted matching terms. Theorem 1 |A(G)| =M(G,w) + U(G,w). Proof. From Lemma 2, the elements of Sp are permutations which are written as products of disjoint cycles σi. An edge eij of G gives rise to a cycle (ij) with weight wp−21 ( √ w2)(−√w2)(−1), i.e. w2wp−21 . Generally a k-matching corresponds to different collections of k disjoint transposi- tions. The resulting matching term is (−w2)k(−1)kwp−2k1 , i.e. wk2wp−2k1 for one of these combinations. Let us consider the product of two cycles which are not transpositions i.e. (i1i2 . . . ik−r)(ik−r+1ik−r+2 . . . ik+r). The weight is (±1)(√w2)k−r(√w2)k−r. This is ±w2kp−2kw1 and is a term of U(G,w). The result follows. The G has no circuits, then Theorem 1 reduces to the following result. Corollary 2 If G has no circuits, then |A(G)| =M(G,w). Proof. If G has no circuits, then there will be no contributing cycles of length greater than 2 which may give rise to unwanted matching terms. The result follows. The following result shows that there is no unwanted term for each cycle having odd length. Lemma 4 If G is circuit with p being an odd integer, then |A(G)| =M(G,w). 54 s. wahid Proof. We show that the weights of the proper cycles of odd length cancel. Let σ = (i1i2 . . . ip−1ip) be proper cycle where p is odd with weight w p/2 2 . In σ we have i1 → i2, i2 → i3, i3 → i4,. . . , ip−1 → ip and ip → i1. Now in σ∗ the reverse orientation (same as σ−1), the cycle is (i1ipip−1 . . . i2i1). In σ−1 we have i1 → ip, ip → ip−1, . . . , i3 → i2 and i2 → i1. The associated weight is now (−1)pwp/22 . Hence the terms cancel and the result follows. The following result is immediate. Theorem 3 If the circuits of G all have odd length, then |A(G)| =M(G,w). Proof. This follows by the use of Lemma 4. The following result gives the unwanted matching terms in an even circuit. Lemma 5 If G is a circuit with p being even, then |A(G)| =M(G,w)± 2wp/22 . Proof. The proof is similar to that of Lemma 4. In this case the weight of the reverse orientation of σ is also (−1)pwp/22 . Clearly the sign of σ∗ and σ is the same and thus the terms do not cancel. The contribution of even cycles is either 2wp/22 or −2wp/22 . The following result gives the expansion of M(G;w) involving the unwanted term for each even circuit. Theorem 4 Let C1, C2, . . . , Cn be the even circuits of a labeled graph G on at least 4 nodes. Then M(G) = |A(G)| − ∑ Ci∈G |A(G −Ci;w)|U(Ci) + ∑ Ci,Cj∈G |A(G − Ci − Cj ;w)|U(Ci)U(Cj) + . . .+ (−1)t|A(G− Ci1 − Ci2 − . . .− Cit ;w)| where we sum over sets of disjoint circuits Ci in G. Proof. We use the principle of Inclusion and Exclusion in the manner described in Lemma 3. In G for an even value of r, there may be more than one circuit on r nodes with 4 ≤ r ≤ p. Let bi be the property that either cycle pii or pi−1i corresponding to the labelled even circuit Ci is a factor in the decomposition of elements Sp for i = 1, 2, . . . , n. Ti = {αi : αi ∈ Sp and has pii or pi−1i as a factor}. Let α ∈ Ti. We define the function f such that f(αi) =weight of αi× sign of αi. Now from lemma 5, both pii and pi−1i have the same weight. Thus f(αi) = 2×(weight of pii)× (weight of remaining factors)×(sign of αi). But weight of pii is U(Ci). The weight of remaining factors times sign of αi are obtained by considering the associated matrix of GCi and its resulting determinant. Thus f(TI) = ∑ αi∈Ti f(αi) = |A(G− Ci)|U(Ci). Therefore ∑n i=1 f(Ti) = ∑n i=1 |A(G− Ci)|U(Ci). The set T is Sp and f(T ) = |A(G)|. Ti,j = {βi : βi ∈ Sp and βi has σi or σ−1i as factors}. f(βi) = 2×(weight σi)×(weight σj)× (weight of remaining factors)×(sign βi). From Lemma 5, this gives U(Ci)U(Cj) times weight of remaining factors and sign βi. We thus remove the two disjoint circuits Ci and Cj from G and find determinant of the determinant of a matching matrix 55 associated matrix i.e |A(G −Ci − Cj)|. Thus ∑n i 6=j f(Ti,j) = ∑n 1≤i 6=j≤n |A(G −Ci − Cj)|U(Ci)U(Cj). The other terms on the right hand side are found likewise. T (1′, 2′, . . . , n′) is the set of permutations of Sp which do not have even cycles (expect two cycles) as factors. This consists of odd cycles of length k where k > 3, one cycle and two cycles. By Lemma 4, there are no unwanted matching terms and thus f(T (1′, 2′, . . . , n′)) = M(G,w). The result follows on adding the respective terms. An illustration We illustrate the result of Theorem 3. Let G be the following labeled graph and its reduction as given by Lemma 1. M(G,w) = (w61 + 5w2w 4 1 + 6w 2 2w 2 1 +w 3 2) + w2(w 4 1 + 4w 2 2w 2 1 + 2w 3 2) + w2(w 4 1 + w 2 2w 2 1) = w61 + 7w2w 4 1 + 11w 2 2 + 3w 3 2. The following table gives the elements of S6 and their weights. Permutation Weight e w61 7 transpositions 7w2w41 11 sets of cycles of form (12)(34) 11w22w 2 1 3 sets of cycles of form (12)(34)(56) 3w32 (1256), (1652), (2345), (2543) 4w22w 2 1 (1256),(34), (1652)(34), (2345)(16), (2543)(16) 4w32 (123456), (165432) 2w32 The even cycles are C1 = (1256), C2 = (2345) and C3 = (123456). The total weights of the permutations listed in first four rows is w61+7w2w 4 1+11w 2 2w 2 1+3w 3 2. This is M(G,w). The total weights of the other permutations is 4w22w 2 1 + 6w 3 2 . This is U(G,w). Now |A(G,w)| = w61 + 7w2w41 + 15w2w21 + 9w32. Also U(C1) = U(C2) = 2w22 and U(C3) = 2w32. Also |A(G − C1);w| = |A(G − C2);w| = w21 + w2 and |A(G − C3), w| = 1. We substitute into Theorem 3 to get (w61 + 7w2w 4 1 + 15w 2 2w 2 1 + 9w 3 2)− 2w22(w21 + w2)− 2w22(w21 + w2)− 2w32 . This is M(G,w). 56 s. wahid 4 Connections with other graph polynomials The characteristic polynomial Φ(B) of a simple graph G is defined as the characteristic polynomial of the adjacency matrix B of G, i.e |xI − B|, where I is the identity matrix and B = (bij) is defined as follows: bij =  1 if nodes i and j are adjacent with i < j −1 if nodes i and j are adjacent with i > j 0 otherwise. It is well known that for a tree T that the matching polynomial M(T ;w′) where w′ = (x,−1), i.e. the acyclic polynomial α(G,x) coincides with the characteristic polynomial Φ(T ;x) (see Godsil and Gutman, [4], [5]). The following result is taken from [4] and Cvetkovic, Doob and Sachs, see [1],[2]. α(G,x) = Φ(B) + 2 ∑ i α(G −Ci;x)− 22 ∑ i 2) in G. In this paper, we modify the definition of A(G) to Aˆ(G) = (aˆij) expressed in terms of complex numbers to facilitate the conversion of M(G,w) to α(G,x), as follows: aˆij =  i √ k if ∃k edges between nodes i and j with i < j −i√k if ∃k edges between nodes i and j with i > j 0 otherwise. The following result is immediate. Lemma 6 The characteristic polynomial of Aˆ(G), i.e. Φ(Aˆ(G)) is the same as Φ(−Aˆ(G)) and is equal to the acyclic polynomial α(G,x). Proof. Now Φ(Aˆ(G)) is |xI − Aˆ(G)|. Also Φ(Aˆ(G)) is the same as |A(D(G))|, where A(D(G)) is the matching matrix of D(G). Then we replace w1 by x and w2 by 1 in the result |A(D(G))|. In order to convert to the acyclic polynomial from |A(D(G))| we place x’s on the leading diagonal and replace √ w2 by complex number i. But this resulting determinant is Φ(−Aˆ(G)). It should be noted that the transpose of Φ(−Aˆ(G)) is Φ(Aˆ(G)). The result follows. The following theorem gives the conversion of Equation (1) above by the use of the matrix Aˆ(G). Theorem 5 Let G be a labeled graph without even circuits. Then Φ(Aˆ(G)) = Φ(B) + 2 ∑ i Φ(Aˆ(G− Ci))− 22 ∑ i Φ(Aˆ(G− Ci − Cj)) + . . . + (−1)t−12t ∑ Φ(Aˆ(G− C1 − C2 − C3 − . . .− Ct)); where Ci are disjoint odd circuits of length greater than 2. determinant of a matching matrix 57 Proof. Now if G has no even circuits, then G is a D-graph. Also Φ(Aˆ(G)) is obtained fromM(G,w) on replacing w1 by x and w2 by −1. This is exactly how α(G,x) is obtained from M(G,w). Thus we replace appropriately in Equation (1). It is interesting to note that α(G,x) can now be written only as determinants for certain graphs. The following theorem shows how α(G,x) is written as the sum of two characteristic polynomials. Theorem 6 Let G be a graph without when circuits and B its adjacency matrix. Then 2α(G,x) = Φ(B) + Φ(−B). Proof. We replace every term except Φ(B) in Theorem 4 by the acyclic polynomial since G is a D-Graph. This gives equation (1) above. A relation between α(G,x) and Φ(−B) is obtained using Lemma 3. In this case we let bi be the property that either cycle pii or pi−1i corresponding to the labeled odd circuit Ci in G is a factor in the decomposition of element of Sp, the other factors being one and /or two cycles. Since B is symmetric then pii or pi−1i have the same weight. The rest of proof is similar to that of Theorem 3. We finally get α(G,x) = Φ(−B)− 2 ∑ i α(G − ci;x) + 22 ∑ i j 0 if nodes vi and vj are not adjacent w1 if i = j The following result is immediate. Theorem 7 Let A∗(G) be as defined above. Then |A ∗( G)| =M(G,w) +R(G,w); where R(G,w) are the terms with square root signs. Proof. This matrix has the same form as A(G). Thus by Theorem 2, all graphs without proper even circuits i.e. D-graphs are such that M(G) = |A∗(G)|. The contribution of even circuits is different. If σ = (i1i2 . . . ir−1ir) is an even cycle associated with an even circuit is G, then in the determinant, we get the term α = √ wi1i2 √ wi2i3 √ wi3i4 · · · √ wi1ir × (−1)r 58 s. wahid where i1 < i2 < . . . < ir. Now σ−1 = (i1irir−1 . . . i3i2). The associated weight in determi- nant is also α. Thus an even circuit in G contributes 2α. The transposition (ixiy) gives a weight √wixiy√wixiy , i.e. wixwiy . Combinations of such terms have no square root signs and one can easily distinguish the matching terms. 6 Discussion The problem of finding a D-graph for a graph G is essentially unsolved. However, a charac- terization of graphs without even cycles has been obtained. The fact that a determinant is used to find the matching polynomial shows that methods of Linear Algebra should be used in investigating properties of the polynomial. Different proofs may be possible for results on acyclic polynomial. For given graphs, if there exists recursive relations for acyclic polynomials then it is possible to find the eigenvalues of Φ(B) without actually finding Φ(B). References [1] Cvetkovic, D.M.; Doob, M.; Sachs, H. (1980) Spectra of Graph-Theory and Applica- tions. Academic Press, New York. [2] Cvetkovic, D.M.; Doob, M.; Gutman, I.; Torgasev, A. (1988) Recent Results in the Theory of Graph Spectra. North-Holland, Amsterdam. [3] Farrell, E.J.; Wahid, S.A. (1995) “D-graphs 1: an introduction to graphs whose match- ing polynomials are determinants of matrices”, Bulletin of the ICA 15: 81–86. [4] Godsil, C.D.; Gutman, I. (1981) “On the theory of the matching polynomial”, Jour. of Graph Theory 5(2): 137-144. [5] Gutman, I.; Cvetkovic, D.M. (1980) “Relations between graphs and special functions”, Collections of Scientific Papers of the Faculty of Science Krakujevac 1: 101-119. [6] Harary, F. (1969) Graph Theory. Addisson-Wesley, Reading Mass.