Namespaces
Variants
Actions

Difference between revisions of "Matching polynomial of a graph"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
(MSC 05C70 05C31)
Line 1: Line 1:
{{TEX|done}}
+
{{TEX|done}}{{MSC|05C70|05C31}}
A matching cover (or simply a matching) in a [[Graph|graph]] $G$ is taken to be a subgraph of $G$ consisting of disjoint (independent) edges of $G$, together with the remaining nodes of $G$ as (isolated) components. A matching is called a $k$-matching if it contains exactly $k$ edges. If $G$ contains $p$ nodes, then the extreme cases are:
+
A matching cover (or simply a matching) in a [[graph]] $G$ is taken to be a subgraph of $G$ consisting of disjoint (independent) edges of $G$, together with the remaining nodes of $G$ as (isolated) components. A matching is called a $k$-matching if it contains exactly $k$ edges. If $G$ contains $p$ nodes, then the extreme cases are:
  
 
i) $p$ is even and $k=p/2$; in this case, all the nodes of $G$ are covered with edges (a [[perfect matching]]); and
 
i) $p$ is even and $k=p/2$; in this case, all the nodes of $G$ are covered with edges (a [[perfect matching]]); and
Line 8: Line 8:
 
The matching polynomial was introduced in [[#References|[a1]]]. Basic algorithms for finding matching polynomials of arbitrary graphs, basic properties of the polynomial, and explicit formulas for the matching polynomials of many well-known families of graphs are given in [[#References|[a1]]]. The coefficients of the polynomial have been investigated [[#References|[a8]]]. The analytical properties of the polynomial have also been investigated [[#References|[a10]]].
 
The matching polynomial was introduced in [[#References|[a1]]]. Basic algorithms for finding matching polynomials of arbitrary graphs, basic properties of the polynomial, and explicit formulas for the matching polynomials of many well-known families of graphs are given in [[#References|[a1]]]. The coefficients of the polynomial have been investigated [[#References|[a8]]]. The analytical properties of the polynomial have also been investigated [[#References|[a10]]].
  
Various polynomials used in statistical physics and in chemical thermodynamics can be shown to be matching polynomials. The matching polynomial is related to many of the well-known classical polynomials encountered in combinatorics. These include the [[Chebyshev polynomials|Chebyshev polynomials]], the [[Hermite polynomials|Hermite polynomials]] and the [[Laguerre polynomials|Laguerre polynomials]]. An account of these and other connections can be found in [[#References|[a14]]], [[#References|[a16]]]. The classical rook polynomial is also a special matching polynomial; and in fact, rook theory can be developed entirely through matching polynomials (see [[#References|[a4]]], [[#References|[a5]]]). The matching polynomial is also related to various other polynomials encountered in graph theory. These include the chromatic polynomial (see [[#References|[a13]]]), the characteristic polynomial and the acyclic polynomial (see [[#References|[a15]]] and [[#References|[a3]]]). The matching polynomial itself is one of a general class of graph polynomials, called F-polynomials (see [[#References|[a2]]]). Two graphs are called co-matching if and only if they have the same matching polynomial. A graph is called matching unique if and only if no other graph has the same matching polynomial. Co-matching graphs and matching unique graphs have been investigated (see [[#References|[a6]]], [[#References|[a9]]]). It has been shown that the matching polynomial of certain graphs (called D-graphs) can be written as determinants of matrices. It appears that for every graph there exists a co-matching D-graph. The construction of co-matching D-graphs is one the main subjects of current interest in the area (see [[#References|[a7]]], [[#References|[a11]]], [[#References|[a12]]]).
+
Various polynomials used in statistical physics and in chemical thermodynamics can be shown to be matching polynomials. The matching polynomial is related to many of the well-known classical polynomials encountered in combinatorics. These include the [[Chebyshev polynomials]], the [[Hermite polynomials]] and the [[Laguerre polynomials]]. An account of these and other connections can be found in [[#References|[a14]]], [[#References|[a16]]]. The classical rook polynomial is also a special matching polynomial; and in fact, rook theory can be developed entirely through matching polynomials (see [[#References|[a4]]], [[#References|[a5]]]). The matching polynomial is also related to various other polynomials encountered in graph theory. These include the chromatic polynomial (see [[#References|[a13]]]), the characteristic polynomial and the acyclic polynomial (see [[#References|[a15]]] and [[#References|[a3]]]). The matching polynomial itself is one of a general class of graph polynomials, called F-polynomials (see [[#References|[a2]]]). Two graphs are called co-matching if and only if they have the same matching polynomial. A graph is called matching unique if and only if no other graph has the same matching polynomial. Co-matching graphs and matching unique graphs have been investigated (see [[#References|[a6]]], [[#References|[a9]]]). It has been shown that the matching polynomial of certain graphs (called D-graphs) can be written as determinants of matrices. It appears that for every graph there exists a co-matching D-graph. The construction of co-matching D-graphs is one the main subjects of current interest in the area (see [[#References|[a7]]], [[#References|[a11]]], [[#References|[a12]]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E.J. Farrell,  "Introduction to matching polynomials"  ''J. Combin. Th. B'' , '''27'''  (1979)  pp. 75–86</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.J. Farrell,  "On a general class of graph polynomials"  ''J. Combin. Th. B'' , '''26'''  (1979)  pp. 111–122</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  E.J. Farrell,  "The matching polynomial and its relation to the acyclic polynomial of a graph"  ''Ars Combinatoria'' , '''9'''  (1980)  pp. 221–228</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E.J. Farrell,  "The matching polynomial and its relation to the Rook polynomial"  ''J. Franklin Inst.'' , '''325''' :  4  (1988)  pp. 527–536</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  E.J. Farrell,  "A graph-theoretic approach to Rook theory"  ''Caribb. J. Math.'' , '''7'''  (1988)  pp. 1–47</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E.J. Farrell,  J.M. Guo,  "On the characterizing properties of the matching polynomial"  ''Vishwa Internat. J. Graph Th.'' , '''2''' :  1  (1993)  pp. 55–62</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "Matching polynomials: A matrix approach and its applications"  ''J. Franklin Inst.'' , '''322'''  (1986)  pp. 13–21</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  E.J. Farrell,  J.M. Guo,  G.M. Constantine,  "On the matching coefficients"  ''Discr. Math.'' , '''89'''  (1991)  pp. 203–210</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "Some general classes of comatching graphs"  ''Internat. J. Math. Math. Sci.'' , '''I0''' :  3  (1987)  pp. 519–524</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "Some analytical properties of the matching polynomial of a graph" , ''Proc. Fifth Caribb. Conf. in Comb. and Graph Th., Jan.5-8, 1988''  pp. 105–119</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "D-graphs I: An introduction to graphs whose matching polynomials are determinants of matrices"  ''Bull. ICA'' , '''15'''  (1995)  pp. 81–86</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "D-graphs II: Constructions of D-graphs for some families of graphs with even cycles"  ''Utilitas Math.'' , '''56'''  (1999)  pp. 167–176</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  E.J. Farrell,  E.G. Whitehead,  "Connections between the matching and chromatic polynomials"  ''Internat. J. Math. Math. Sci.'' , '''15''' :  4  (1992)  pp. 757–766</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  I. Gutman,  "The matching polynomial"  ''MATCH'' :  6  (1979)  pp. 75–91</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  I. Gutman,  "The acyclic polynomial of a graph"  ''Publ. Inst. Math. Beograd'' , '''22 (36)'''  (1977)  pp. 63–69</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  C.D. Godsil,  I. Gutman,  "On the theory of the matching polynomial"  ''J. Graph Th.'' , '''5'''  (1981)  pp. 137–145</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  E.J. Farrell,  "Introduction to matching polynomials"  ''J. Combin. Th. B'' , '''27'''  (1979)  pp. 75–86</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  E.J. Farrell,  "On a general class of graph polynomials"  ''J. Combin. Th. B'' , '''26'''  (1979)  pp. 111–122</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  E.J. Farrell,  "The matching polynomial and its relation to the acyclic polynomial of a graph"  ''Ars Combinatoria'' , '''9'''  (1980)  pp. 221–228</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  E.J. Farrell,  "The matching polynomial and its relation to the Rook polynomial"  ''J. Franklin Inst.'' , '''325''' :  4  (1988)  pp. 527–536</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  E.J. Farrell,  "A graph-theoretic approach to Rook theory"  ''Caribb. J. Math.'' , '''7'''  (1988)  pp. 1–47</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  E.J. Farrell,  J.M. Guo,  "On the characterizing properties of the matching polynomial"  ''Vishwa Internat. J. Graph Th.'' , '''2''' :  1  (1993)  pp. 55–62</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "Matching polynomials: A matrix approach and its applications"  ''J. Franklin Inst.'' , '''322'''  (1986)  pp. 13–21</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top">  E.J. Farrell,  J.M. Guo,  G.M. Constantine,  "On the matching coefficients"  ''Discr. Math.'' , '''89'''  (1991)  pp. 203–210</TD></TR>
 +
<TR><TD valign="top">[a9]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "Some general classes of comatching graphs"  ''Internat. J. Math. Math. Sci.'' , '''I0''' :  3  (1987)  pp. 519–524</TD></TR>
 +
<TR><TD valign="top">[a10]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "Some analytical properties of the matching polynomial of a graph" , ''Proc. Fifth Caribb. Conf. in Comb. and Graph Th., Jan.5-8, 1988''  pp. 105–119</TD></TR>
 +
<TR><TD valign="top">[a11]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "D-graphs I: An introduction to graphs whose matching polynomials are determinants of matrices"  ''Bull. ICA'' , '''15'''  (1995)  pp. 81–86</TD></TR>
 +
<TR><TD valign="top">[a12]</TD> <TD valign="top">  E.J. Farrell,  S.A. Wahid,  "D-graphs II: Constructions of D-graphs for some families of graphs with even cycles"  ''Utilitas Math.'' , '''56'''  (1999)  pp. 167–176</TD></TR>
 +
<TR><TD valign="top">[a13]</TD> <TD valign="top">  E.J. Farrell,  E.G. Whitehead,  "Connections between the matching and chromatic polynomials"  ''Internat. J. Math. Math. Sci.'' , '''15''' :  4  (1992)  pp. 757–766</TD></TR>
 +
<TR><TD valign="top">[a14]</TD> <TD valign="top">  I. Gutman,  "The matching polynomial"  ''MATCH'' :  6  (1979)  pp. 75–91</TD></TR>
 +
<TR><TD valign="top">[a15]</TD> <TD valign="top">  I. Gutman,  "The acyclic polynomial of a graph"  ''Publ. Inst. Math. Beograd'' , '''22 (36)'''  (1977)  pp. 63–69</TD></TR>
 +
<TR><TD valign="top">[a16]</TD> <TD valign="top">  C.D. Godsil,  I. Gutman,  "On the theory of the matching polynomial"  ''J. Graph Th.'' , '''5'''  (1981)  pp. 137–145</TD></TR>
 +
</table>

Revision as of 16:38, 7 January 2015

2020 Mathematics Subject Classification: Primary: 05C70 Secondary: 05C31 [MSN][ZBL] A matching cover (or simply a matching) in a graph $G$ is taken to be a subgraph of $G$ consisting of disjoint (independent) edges of $G$, together with the remaining nodes of $G$ as (isolated) components. A matching is called a $k$-matching if it contains exactly $k$ edges. If $G$ contains $p$ nodes, then the extreme cases are:

i) $p$ is even and $k=p/2$; in this case, all the nodes of $G$ are covered with edges (a perfect matching); and

ii) $k=0$; in this case, none of the nodes of $G$ are covered by edges (the empty graph). If a matching contains $k$ edges, then it will have $p-2k$ component nodes. Now assign weights (or indeterminates over the complex numbers) $w_1$ and $w_2$ to each node and edge of $G$, respectively. Take the weight of a matching to be the product of the weights of all its components. Then the weight of a $k$-matching will be $w_1^{p-2k}w_2^k$. The matching polynomial of $G$, denoted by $M(G;w)$, is the sum of the weights of all the matchings in $G$. Setting $w_1=w_2=w$, then the resulting polynomial is called the simple matching polynomial of $G$.

The matching polynomial was introduced in [a1]. Basic algorithms for finding matching polynomials of arbitrary graphs, basic properties of the polynomial, and explicit formulas for the matching polynomials of many well-known families of graphs are given in [a1]. The coefficients of the polynomial have been investigated [a8]. The analytical properties of the polynomial have also been investigated [a10].

Various polynomials used in statistical physics and in chemical thermodynamics can be shown to be matching polynomials. The matching polynomial is related to many of the well-known classical polynomials encountered in combinatorics. These include the Chebyshev polynomials, the Hermite polynomials and the Laguerre polynomials. An account of these and other connections can be found in [a14], [a16]. The classical rook polynomial is also a special matching polynomial; and in fact, rook theory can be developed entirely through matching polynomials (see [a4], [a5]). The matching polynomial is also related to various other polynomials encountered in graph theory. These include the chromatic polynomial (see [a13]), the characteristic polynomial and the acyclic polynomial (see [a15] and [a3]). The matching polynomial itself is one of a general class of graph polynomials, called F-polynomials (see [a2]). Two graphs are called co-matching if and only if they have the same matching polynomial. A graph is called matching unique if and only if no other graph has the same matching polynomial. Co-matching graphs and matching unique graphs have been investigated (see [a6], [a9]). It has been shown that the matching polynomial of certain graphs (called D-graphs) can be written as determinants of matrices. It appears that for every graph there exists a co-matching D-graph. The construction of co-matching D-graphs is one the main subjects of current interest in the area (see [a7], [a11], [a12]).

References

[a1] E.J. Farrell, "Introduction to matching polynomials" J. Combin. Th. B , 27 (1979) pp. 75–86
[a2] E.J. Farrell, "On a general class of graph polynomials" J. Combin. Th. B , 26 (1979) pp. 111–122
[a3] E.J. Farrell, "The matching polynomial and its relation to the acyclic polynomial of a graph" Ars Combinatoria , 9 (1980) pp. 221–228
[a4] E.J. Farrell, "The matching polynomial and its relation to the Rook polynomial" J. Franklin Inst. , 325 : 4 (1988) pp. 527–536
[a5] E.J. Farrell, "A graph-theoretic approach to Rook theory" Caribb. J. Math. , 7 (1988) pp. 1–47
[a6] E.J. Farrell, J.M. Guo, "On the characterizing properties of the matching polynomial" Vishwa Internat. J. Graph Th. , 2 : 1 (1993) pp. 55–62
[a7] E.J. Farrell, S.A. Wahid, "Matching polynomials: A matrix approach and its applications" J. Franklin Inst. , 322 (1986) pp. 13–21
[a8] E.J. Farrell, J.M. Guo, G.M. Constantine, "On the matching coefficients" Discr. Math. , 89 (1991) pp. 203–210
[a9] E.J. Farrell, S.A. Wahid, "Some general classes of comatching graphs" Internat. J. Math. Math. Sci. , I0 : 3 (1987) pp. 519–524
[a10] E.J. Farrell, S.A. Wahid, "Some analytical properties of the matching polynomial of a graph" , Proc. Fifth Caribb. Conf. in Comb. and Graph Th., Jan.5-8, 1988 pp. 105–119
[a11] E.J. Farrell, S.A. Wahid, "D-graphs I: An introduction to graphs whose matching polynomials are determinants of matrices" Bull. ICA , 15 (1995) pp. 81–86
[a12] E.J. Farrell, S.A. Wahid, "D-graphs II: Constructions of D-graphs for some families of graphs with even cycles" Utilitas Math. , 56 (1999) pp. 167–176
[a13] E.J. Farrell, E.G. Whitehead, "Connections between the matching and chromatic polynomials" Internat. J. Math. Math. Sci. , 15 : 4 (1992) pp. 757–766
[a14] I. Gutman, "The matching polynomial" MATCH : 6 (1979) pp. 75–91
[a15] I. Gutman, "The acyclic polynomial of a graph" Publ. Inst. Math. Beograd , 22 (36) (1977) pp. 63–69
[a16] C.D. Godsil, I. Gutman, "On the theory of the matching polynomial" J. Graph Th. , 5 (1981) pp. 137–145
How to Cite This Entry:
Matching polynomial of a graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matching_polynomial_of_a_graph&oldid=36121
This article was adapted from an original article by E.J. Farrell (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article