$PC$-polynomial of graph

Abstract

We define $PC$-polynomial of graph which is related to clique, (in)dependence and matching polynomials. The growth rate of partially commutative monoid is equal to the largest root $\beta (G)$ of $PC$-polynomial of the corresponding graph. The random algebra is defined in such way that its growth rate equals the largest root of $PC$-polynomial of random graph. We prove that for almost all graphs all sufficiently large real roots of $PC$-polynomial lie in neighbourhoods of roots of $PC$-polynomial of random graph. We show how to calculate the series expansions of the latter roots. The average value of $\beta (G)$ over all graphs with the same number of vertices is computed. We found the graphs on which the maximal value of $\beta (G)$ with fixed numbers of vertices and edges is reached. From this, we derive the upper bound of $\beta (G)$. Modulo one assumption, we do the same for minimal value of $\beta (G)$. We study the Nordhaus---Gaddum bounds of $\beta (G)+\beta (\bar{G})$ and $\beta (G)\beta (\bar{G})$.

arXiv comment118 p. (8 figures, 1 table). It's also a survey on clique-type polynomials. Any comments are welcome!

References in corpus (13)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The Clique Density Theorem
• Embedability between right-angled Artin groups
• Upper tails and independence polynomials in random graphs
• On the average size of independent sets in triangle-free graphs
• Extremal regular graphs: the case of the infinite regular tree
• On a conjecture of Sokal concerning roots of the independence polynomial
• The independent set sequence of some families of trees
• Growth in Right-Angled Groups and Monoids
• On P-unique hypergraphs
• On trees with real rooted independence polynomial
• On the Stability of Independence Polynomials
• Unimodality of the independence polynomials of non-regular caterpillars