CanaDAM 2021
On-line, May 25 - 28, 2021

Graph Polynomials - Part II
Org: Iain Beaton (Dalhousie University) and Ben Cameron (University of Guelph)

FERENC BENCS, Alfréd Rényi Institute of Mathematics
Zero-free regions for some graph polynomials.  [PDF]

In this talk, I will show regions that contain no zeros in the complex plane for some graph polynomials. The edge cover polynomial of a graph $G$ is the generating function of edges, that covers $V(G)$. It is known that the zeros of this polynomial have length at most $\frac{(2+\sqrt{3})^2}{1+\sqrt{3}}$, that we strengthen by showing that it is at most $4$. We use the general subgraph counting polynomial of Wagner to establish this result along with its generalization for hypergraphs, and to obtain further results for another graph polynomial. Joint work with Péter Csikvári and Guus Regts.

JASON BROWN, Dalhousie University
Recent Results in Network Reliability  [PDF]

Network reliability is a probabilistic model of a graph’s robustness to independent failures of either edges or vertices (or both); under a variety of scenarios, the functions turn out to be polynomials that encode important combinatorial information. In this talk we will survey some recent results, focusing particular attention on the roots of these polynomials.

BEN CAMERON, University of Guelph
The largest real root of the independence polynomial of a unicyclic graph  [PDF]

The independence polynomial of a graph $G$, denoted $I(G,x)$, is the generating polynomial for the number of independent sets of each size. It is known that for every graph $G$, the root of $I(G,x)$ of smallest modulus, denoted $\xi(G)$, is real. Extending results due to Csikvári (2013) and answering an open question due to Oboudi (2018), we find the graphs that minimize/maximize $\xi(G)$ among all connected (well-covered) unicyclic graphs. Our methods involve showing a stronger result on a partial order on graphs induced by their independence polynomials evaluated at small negative values. This is joint work with Iain Beaton.

PÉTER CSIKVÁRI, Eötvös Loránd University
Evaluations of Tutte polynomials of large girth regular graphs  [PDF]

In this talk we study Tutte polynomials of regular graphs. Let $T_G(x,y)$ be the Tutte polynomial of a graph $G$ with $v(G)$ vertices. Let $(G_n)_n$ be a sequence of $d$-regular graphs with girth $g(G_n)\to \infty$. (Girth is the length of the shortest cycle.) We determine the limit $$\lim_{n \to \infty}T_{G_n}(x,y)^{1/v(G_n)}$$ for $0\leq y\leq 1$ and $x\geq 1$. In particular, we determine the limit value for the number of spanning forests (the value of $T_G(2,1)$) and for the number of acyclic orientations (the value of $T_G(2,0)$). Joint work with Ferenc Bencs.

STEPHAN WAGNER, Uppsala University
Distribution of the coefficients of the subtree polynomial  [PDF]

A subtree of a graph is a (not necessarily induced) subgraph that is also a tree. Writing $s_k(G)$ for the number of $k$-vertex subtrees of a graph $G$, the subtree polynomial of $G$ is the polynomial $S(G,x) = \sum_{k \geq 0} s_k(G)x^k$. In this talk, some recent results on the distribution of the coefficients and related questions regarding the subtree polynomial will be discussed. In particular, we consider the situation where $G$ is a random graph or tree.