Matching polynomial

We mention in passing that the zeros of the matching polynomial, namely the numbers Yi, Y2, > yn> are always real-valued [42, 54],... 

Gutman, I. (1992b). Some Analytical Properties of the Independence and Matching Polynomials. MATCH (Comm.Math.Comp.Chem.), 28,139-150. 

Hosoya, H. and Ohkami, N. (1983). Operator Technique for Obtaining the Recursion Formulas of Characteristic and Matching Polynomials as Applied to Polyhex Graphs. J.Comput.Chem., 4,585-593. 

Salvador, J.M., Hernandez, A., Beltram, A., Duran, R. and Mactutis, A. (1998). Fast Partial-Differential Synthesis of the Matching Polynomial of C72-ioo- J.Chem.InfComput.ScL, 38,1105-1110. 

Several polynomials associated with graphs were defined, such as the characteristic polynomials, counting polynomials, —> matching polynomial, chromatic polynomial, and Tutte... 

Characteristic polynomials belong to a more general class of graph polynomials, which are used to encode some information on molecular graphs. Among these, there are Z-counting polynomial, —> matching polynomial, and Wiener polynomial. 

Cluj polynomials, matching polynomial, and omega polynomial. 

Closely related to the Z-counting polynomial, the matching polynomial (or acyclic polynomial... 

For acyclic graphs, the matching polynomial coincides with the —> graph characteristic polynomial. Moreover, it was demonstrated the following relationship between the Z-counting and matching polynomials [Hosoya, 2003] ... 

For acyclic graphs the Z-counting polynomial coefficients a((5, k) coincide with the absolute values of the coefficients of the characteristic polynomial of the adjacency matrix (i.e., graph characteristic polynomial) [Nikolic, PlavSic et al., 1992]. Therefore, for any graph, the Hosoya Z index can also be calculated from the matching polynomial coefficients m2k as... 

From the matching polynomial or the characteristic polynomial, the Hosoya Z index is... 

Gutman, 1. (1979) The matching polynomial. MATCH Commun. Math. Comput. Chem., 6, 75-91. 

Gutman, 1. (1983) Characteristic and matching polynomials of benzenoid hydrocarbons./. Chem. Soc. Faraday Trans II, 79, 337-345. 

Gutman, L, Graovac, A. and Mohar, B. (1982) On the existence of a Hermitian matrix whose characteristic polynomial is the matching polynomial of a molecular graph. MATCH Commun. Math. Comput. Chem., 13, 129-150. 

If the summation in eq.(57) is performed only over those permutations P C P produced by independent transpositions, the acyclic or matching polynomial a( 7,A) of the graph Q is derived. The transpositions involved here have the cycle structure The acyclic... 

The theory of aromaticity, based on the so-called topoio cal resonance energy, requires knowledge of the zeros of the matching polynomial. 

The monomer-dimer model of statistical physics describes a simple system in which phase transitions can occur. It too makes use of the matching polynomial. 

The coeffidents and zeros of the characteristic and matching polynomials reflect the extent of branching in the skeleton of a molecule. Accord-... 

The next discoverer of the matching polynomial was Hosoya [43,44], who considered the polynomial Af(G,x) of the molecular graph of a saturated hydrocarbon. In particular, Hosoya noticed that the total number of matchings in G, namely... 

The matching polynomial Ma(G,x) was introduced by Gutman et al [68-71] in connection with the theory of the so-called topolofpcal resonance energy (see later). In these papers Ma(G,x) was referred to as the "acyclic polynomial . Independently, Aihara [72] develc ed a fully equivalent resonance energy concept he named Ma(( ,x) the "reference p ynomial . 

Obviously unaware of all this previous work, Farrell published In 1979 a mathematical paper [73], introducing the matching polynomial for the sixth time. In fact, there is a slight and inessential difference [74] between Farrell s "matching pdynomial and the matching polynomi defined in the present work. 

In concluding this short hist<, it should also be mentioned that there is a cl< rdation between the so-called rook polynomial [75] and the matching polynomial. Every rook pdynomial coincides with the matching polynomial of a bipartite graph [76]. 

The theory of the matching polynomial has been expounded in greater detail in [77, 78, 157]. Methods for computation of the matching polynomial are outlined in [197]. 

Using the result 4.5.1.12 we can derive a sample recurrence relation for the matching polynomial of the complete graph Kn Since every vertex V of has exactly n - 1 neighbors sey) and since... 

If one compares the definition of the characteristic polynomial (4.4.1.1) with that of the matching polynomial (4.5.1.3)f the wrong impression may be obtained that these two graphic polynomials have hardly any common feature. That this is not so will be demonstrated in the present section. The relations between Ma(G) and Ch(G) represent an important and nontrivial part of the theory of matching polynomiab and are of the greatest value in chemical applications ... 

The right hand side of the above relation is obviously the matching polynomial of G. 

A few years ago Godsil [84] discovered another relation between Ma and Ch. This seems to be a crucial result in the theory of the matching polynomial. 

The main merit of Theorem 4.S.2.7 is that it reduces the entire theory of the matching polynomial to the much more developed graph spectral theory. It is thus now no longer surprising that there are numerous analogies between Ma(G) and Ch(G). We list two more results of this kind [97-98], and refer the interested reader to reference [99] ... 

One way in which the matching polynomial was discovered (68-70,72] was to modify Sachs theorem (4.4.3.2 and 4.4.S.3). Thus, instead of Ddinitimi 4.5.1.3 we can introduce the matching pdynomial via the following statement resembling Sachs themem ... 

Thbo EM. Every matching polynomial is an independence polynomial,... 

---