Speaker 1: Isaac McMullin
Existence of Optimal Split Reliability Polynomials
One of the most common models of robustness of a graph against random failures has all vertices operational, but the edges independently operational with probability p. On one hand, one can ask for the probability that all vertices can communicate (all-terminal reliability) while on the other hand, we can ask that two specific vertices (or terminals) can communicate with each other (two-terminal reliability). While both of these questions have been well-studied, they are both increasing functions of the edge probability. One new approach is split reliability, where for two fixed vertices s and t, we consider the probability that every vertex communicates with one of s or t, but not both. The split reliability of G is a polynomial function of p that for connected graphs is 0 both at p=0 and at p=1. In this presentation, we explore the existence for fixed numbers n>=2 and m>=n-1 of an optimal connected (n,m)-graph G_(n,m) for split reliability, that is, a connected graph with n vertices and m edges for which for any other such graph H, the split reliability of G_(n,m) is at least as large as that of H, for all values of p in [0,1]. Unlike the similar problems for all-terminal and two-terminal reliability, where only partial results are known, we completely solve the issue for split reliability, where we show that there is an optimal (n,m)-graph for split reliability if and only if n<=3, m=n-1, or n=m=4.
Speaker 2: Ian George
Degree Polynomials of Graphs
In this talk we introduce the Degree Polynomial of a graph. This polynomial is defined to be the generating function of the sequence (a_0, a_1, a_2, …) where a_k is the number of vertices of degree k in a graph. Little has been published about this polynomial other than its behaviour under graph operations. We will explore some basic properties of this polynomial, and see what information it encodes about a graph. Then we will discuss the roots of degree polynomials, or degree roots, giving some bounds and density results. Along the way, the degree polynomials and degree roots for certain families of graphs will be highlighted.
