Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs. (English) Zbl 1239.05096
Summary: The independence polynomial of a graph \(G\) is the polynomial \(\sum_{l}x^|l|\), summed over all independent subsets \(I\subseteq V(G)\). We show that if \(G\) is clawfree, then there exists a Mehler formula for its independence polynomial. This was proved for matching polynomials in B. Lass [Combinatorica 24, No. 3, 427–440 (2004; Zbl 1064.05122)] and extends the combinatorial proof of the Mehler formula found by D. Foata [J. Comb. Theory, Ser. A 24, 367–376 (1978; Zbl 0401.33008)]. It implies immediately that all the roots of the independence polynomial of a clawfree graph are real, answering a question posed by Y. O. Hamidoune [J. Comb. Theory, Ser. B 50, No.2, 241-244 (1990; Zbl 0743.05029)] and R. P. Stanley [Discrete Math. 193, No. 1–3, 267-286 (1998; Zbl 1061.05508)] and solved by M. Chudnovsky and P. Seymour [J. Comb. Theory, Ser. B 97, No. 3, 350–357 (2007; Zbl 1119.05075)]. We also prove a Mehler formula for the multivariate matching polynomial, extending results of B. Lass [loc. cit.].
MSC:
| 05C31 | Graph polynomials |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05A15 | Exact enumeration problems, generating functions |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Keywords:
independence polynomial; roots; clawfree graphs; matching polynomial; monomer dimer systems; mehler formula; Hermite polynomial; algebra of set functions; partitions of setsReferences:
| [1] | Brown, J. I.; Nowakowski, R., Bounding the roots of independence polynomials, Ars Combin., 58, 113-120 (2001) · Zbl 1065.05051 |
| [2] | Brown, J. I.; Nowakowski, R., Average independence polynomials, J. Combin. Theory Ser. B, 93, 313-318 (2005) · Zbl 1056.05105 |
| [3] | Brown, J. I.; Dilcher, K.; Nowakowski, R. J., Roots of independence polynomials of well-covered graphs, J. Algebraic Combin., 11, 197-210 (2000) · Zbl 0994.05109 |
| [4] | Brown, J. I.; Hickman, C. A.; Nowakowski, R. J., On the location of roots of independence polynomials, J. Algebraic Combin., 19, 273-282 (2004) · Zbl 1043.05087 |
| [5] | Choe, Y. B.; Oxley, J. G.; Sokal, A. D.; Wagner, D. G., Homogeneous multivariate polynomials with the half-plane property, Adv. in Appl. Math., 32, 88-187 (2004), Special issue on the Tutte polynomial · Zbl 1054.05024 |
| [6] | Chudnovsky, M.; Seymour, P., The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B, 97, 350-357 (2007) · Zbl 1119.05075 |
| [7] | Engström, A., Inequalities on well-distributed point sets on circles, JIPAM. J. Inequal. Pure Appl. Math., 8, 2 (2007), Article 34, 5 pp. (electronic) · Zbl 1370.52007 |
| [8] | Fisher, D. C.; Solow, A. E., Dependence polynomials, Discrete Math., 82, 251-258 (1990) · Zbl 0721.05036 |
| [9] | Foata, D., A combinatorial proof of the Mehler formula, J. Combin. Theory Ser. A, 24, 367-376 (1978) · Zbl 0401.33008 |
| [10] | Godsil, C. D., Algebraic Combinatorics (1993), Chapman & Hall · Zbl 0814.05075 |
| [11] | Godsil, C. D., Hermite polynomials and a duality relation for matchings polynomials, Combinatorica, 1, 257-262 (1981) · Zbl 0495.05005 |
| [12] | Gutman, I., An identity for the independence polynomial of trees, Publ. Inst. Math. (Belgrade), 50, 19-23 (1991) · Zbl 0763.05026 |
| [13] | Gutman, I., Some analytic properties of the independence and matching polynomials, MATCH Commun. Math. Comput. Chem., 28, 139-150 (1992) · Zbl 0767.05070 |
| [14] | Hamidoune, Y. O., On the numbers of independent \(k\)-sets in a clawfree graph, J. Combin. Theory Ser. B, 50, 241-244 (1990) · Zbl 0743.05029 |
| [15] | Heilmann, O. J.; Lieb, E. H., Theory of monomer-dimer systems, Comm. Math. Phys., 25, 190-232 (1972) · Zbl 0228.05131 |
| [16] | Hoede, C.; Li, X., Clique polynomials and independent set polynomials of graphs, Discrete Math., 25, 219-228 (1994) · Zbl 0799.05030 |
| [17] | Jackson, B.; Sokal, A. D., Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids, J. Combin. Theory Ser. B, 99, 869-903 (2009) · Zbl 1221.05144 |
| [18] | Lang, S., Algebra, Grad. Texts in Math., vol. 211 (2002), Springer-Verlag: Springer-Verlag New York · Zbl 0984.00001 |
| [19] | Lass, B., Matching polynomials and duality, Combinatorica, 24, 427-440 (2004) · Zbl 1064.05122 |
| [20] | Lass, B., Orientations acycliques et le polynôme chromatique, European J. Combin., 22, 1101-1123 (2001) · Zbl 0990.05063 |
| [21] | Lass, B., The \(N\)-dimensional matching polynomial, Geom. Funct. Anal., 15, 453-475 (2005) · Zbl 1074.05073 |
| [22] | Lass, B., Variations sur le thème \(E + \overline{E} = X Y\), Adv. in Appl. Math., 29, 215-242 (2002) · Zbl 1015.05005 |
| [23] | Lavallée, S.; Reutenauer, C., Characteristic polynomials of nonnegative integral square matrices and clique polynomials, Sém. Lothar. Combin., 61A (2009), Art. B61Ac, 11 pp · Zbl 1283.05137 |
| [24] | Levit, V. E.; Mandrescu, E., The independence polynomial of a graph - a survey, (Proceedings of the 1st International Conference on Algebraic Informatics (2005), Aristotle Univ. Thessaloniki: Aristotle Univ. Thessaloniki Thessaloniki), 233-254 |
| [25] | Qian, J.; Dress, A.; Wang, Y., On the dependence polynomial of a graph, European J. Combin., 28, 337-346 (2007) · Zbl 1110.05036 |
| [26] | Scott, A. D.; Sokal, A. D., The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys., 118, 1151-1261 (2005) · Zbl 1107.82013 |
| [27] | Scott, A. D.; Sokal, A. D., On dependency graphs and the lattice gas, Combin. Probab. Comput., 15, 253-279 (2006) · Zbl 1138.05323 |
| [28] | Stanley, R. P., Graph colorings and related symmetric functions: Ideas and applications, Discrete Math., 193, 267-286 (1998) · Zbl 1061.05508 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
