ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 20(1) (2000) 57-69
DOI: 10.7151/dmgt.1106


Jorge Luis Arocha and Bernardo Llano

Instituto de Matemáticas, UNAM, Circuito Exterior
Ciudad Universitaria, México, D.F. 04510



The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.

Keywords: matching, matching polynomial, dominating set.

1991 Mathematics Subject Classification: Primary 05C70, 05A15.


[1] J.L. Arocha, Anticadenas en conjuntos ordenados, An. Inst. Mat. Univ. Nac. Autónoma México 27 (1987) 1-21.
[2] C. Berge, Graphs and Hypergraphs (North-Holland, London, 1973).
[3] E.J. Farrell, An introduction to matching polynomials, J. Combin. Theory (B) 27 (1979) 75-86, doi: 10.1016/0095-8956(79)90070-4.
[4] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, New York, 1979).
[5] C.D. Godsil and I. Gutman, On the theory of the matching polynomial, J. Graph Theory 5 (1981) 137-144, doi: 10.1002/jgt.3190050203.
[6] C.D. Godsil, Algebraic Combinatorics (Chapman and Hall, New York, 1993).
[7] O.J. Heilmann and E.H. Lieb, Monomers and dimers, Phys. Rev. Lett. 24 (1970) 1412-1414, doi: 10.1103/PhysRevLett.24.1412.
[8] O.J. Heilmann and E.H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972) 190-232, doi: 10.1007/BF01877590.
[9] M.A. Henning, O.R. Oellermann and H.C. Swart, The diversity of domination, Discrete Math. 161 (1996) 161-173, doi: 10.1016/0012-365X(95)00074-7.
[10] N.N. Lebedev, Special Functions and their Applications (Dover, New York, 1972).
[11] L. Lovász, Combinatorial Problems and Exercises (North-Holland, Amsterdam, 1979).
[12] O. Ore, Theory of Graphs (Amer. Math. Soc., Providence, 1962).

Received 3 February 1999
Revised 6 May 1999