Graph Polynomials II
[PDF]

LLUIS VENA CROS, University of Amsterdam
A Tutte polynomial for graphs embedded on surfaces  [PDF]

In this talk, we present a graph polynomial for maps (graphs embedded in orientable surfaces) that contains the Las Vergnas polynomial, Bollob\'as-Riordan polynomial and Kruskhal polynomial as specialisations.

The new polynomial invariant of maps is built following Tutte's construction of the dichromate of a graph (that is, the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial. In our case, we consider the analogues for maps of the chromatic polynomial (local tensions) and of the flow polynomial (local flows). Hence, by construction, the new polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests.

An extension of the polynomial to graphs embedded on non-orientable surfaces is also discussed.

This is a joint work with Andrew Goodall, Thomas Krajewski, Guus Regts and Bart Litjens.

HOSSEIN TEIMOORI FAAL, Allameh Tabatabai University, Tehran, Iran
Kelly-Type Subgraph Counting Identities and Clique Polynomials  [PDF]

Subgraph counting identities play an essential role in reconstruction problems for graphs. Vertex and Edge - Kelly Lemmas are two key lemmas in the theory of graph reconstructions. The clique polynomial of a graph $G$ is the polynomial $C(G,x):= 1 + \sum_{\emptyset \neq U \subseteq V(G)}x^{\vert U \vert}$, where the sum runs over all induced subgraphs $G[U]$ that are cliques in $G$. \In this talk while reviewing Kelly's subgraph counting lemmas, we will obtain other Kelly - type subgraph counting identities. We will also give several new graph - theoretical interpretations of the first and higher order derivatives of the clique polynomial of a finite simple graph. Finally, we will use the above new interpretations along with the interlacing theory of polynomials to provide some bounds on the number of the real roots of the clique polynomials of several important classes of graphs, including chordal and planar graphs.

GUUS REGTS, University of Amsterdam
Nonvanishing domains of the independence polynomial  [PDF]

Sokal conjectured about 15 years ago that there exists an open region $D$ in the complex plane that contains the interval $[0,\lambda_\Delta)$ for some constant $\lambda_\Delta>0$ such that the independence polynomial of any graph of maximum degree at most $\Delta$ does not vanish on $D$. In joint work with Han Peters we have settled this conjecture using complex dynamical systems. In this talk I will explain the connection between zeros of the independence polynomial and complex dynamical systems and give some ideas of our proof of this result. I will also explain how, based on a recent line of work initiated by Barvinok, this result gives an efficient algorithm for approximating evaluations of the independence polynomial on $D$.

MICHAEL YATAURO, Penn State University
Probability Polynomials Associated with Edge Covers of a Graph  [PDF]

Let $G$ be a finite simple graph. Assume edges of $G$ are selected independently with probability $\rho$, for $0<\rho<1$. The edge reliability polynomial of $G$, denoted $R(G,\rho)$, is the polynomial in $\rho$ which calculates the probability that a randomly selected set of edges in $G$ forms an edge cover of $G$. If $\mathcal{G}$ is a class of graphs, we say $H\in \mathcal{G}$ is uniformly most (resp. least) reliable if $R(H,\rho)\geq R(G,\rho)$ (resp. $R(H,\rho)\leq R(G,\rho)$) for all $G\in \mathcal{G}$ and for all $\rho\in(0,1)$. We will discuss the edge reliability polynomials of trees, unicyclic graphs, and connected graphs having one more edge than the number of vertices. In particular, we provide a survey of results which demonstrate the uniformly most/least reliable graphs within these three classes.