Invited Paper Session Abstracts - Eigenvalues and Graphs

Given a graph \(G\) representing a contact network for individuals in a community in which an infectious disease is spreading, there is a wide range of measures by which we may determine the most pivotal nodes (or individuals) in terms of the role they play in the spread of the disease. Many of these depend on spectral information associated with a matrix representation of the graph. In this talk, we give an overview of such centrality measures, and demonstrate simulation results which compare the different centrality measures and determine their effectiveness in establishing vaccination or testing strategies to control the disease.

In this talk, we introduce a Fielder vector, which is used for the graph partitioning problem, to partition a graph (according to its sign pattern) into two connected subgraphs that are similar in size. Our work is motivated by graphs having Fiedler vectors with unbalanced sign patterns such that a partition can result in two connected subgraphs that are distinctly different in size. A characterization of graphs having a Fiedler vector with exactly one negative component is presented, and some classes of such graphs are shown. In particular, we describe graphs such that any Fiedler vector has only either one negative or one positive sign.

Given a graph \(G\), the exponential distance matrix is defined entry-wise by letting the \((u,v)\)-entry be \(q^{dist(u,v)}\) where \(dist(u,v)\) is the distance between the vertices \(u\) and \(v\) with the convention that if vertices are in different components, then \(q^{dist(u,v)}=0\). We establish several properties of the characteristic polynomial (spectrum) for this matrix and the inertia of some graph families.

In this talk we will discuss what subgraphs can be guaranteed if a graph has a large eigenvalue. This is the spectral analog of the Turán problem and was first raised by Brualdi and Solheid and Nikiforov. We will give an overview of how to prove theorems in this area and will discuss some intuition for how to guess what the extremal graph(s) should be. This is joint work with Sebi Cioaba, Dheer Desai, Lihua Feng, Josh Tobin, and Xiao-Dong Zhang.

In the same way that Brownian motion can be modelled by random walks, the movement of quantum particles can be modelled by quantum walks. Given a graph and an associated Hermitian matrix \(H\), a quantum walk on the graph is defined as a function of a time \(t\) by \(exp(itH)\), and using spectral decomposition, we can study quantum walks on graphs by studying the eigenvalues. In this talk, we will give an overview of quantum walks on graphs, focusing on the behaviors that set them apart from their classical counterparts and spectral characterization of such behaviors.

In 1970s, Ron Graham and Henry Pollak introduced the notion of graph addressing which is a labeling of the vertices of an undirected graph by words of the same length over the alphabet {0,1,*} such that the distance between any two vertices equals the number of positions in their labels/addresses where one vertex has a 0 and the other one has a 1. The minimum of length of such words has been investigated by various people and is closely related to the partition of the edge set of the graph into bicliques (complete bipartite subgraphs). In this talk, I will describe the connection between these problems and the eigenvalues of a graph, some recent results related to this parameter for various families of graphs and present several open problems.