You are here

Invited Paper Session Abstracts - Eigenvalues and Graphs

Please note: all sessions are listed in Mountain Daylight Time (MDT = UTC-6:00)

Thursday, August 5, 1:00 p.m. - 4:00 p.m.

Graphs can be used to represent the relations (edges) between objects (vertices), and so play an important role both in theoretical as well as applied settings. One important tool in understanding graphs is through the use of the eigenvalues and eigenvectors of matrices associated with graphs; this is sometimes known as spectral graph theory. There are many possible matrices that can be explored and each one brings its own strengths and weaknesses into understanding graphs. This session will bring together a variety of viewpoints of how eigenvalues and graphs are connected.

Graphs, Eigenvalues, and COVID-19

1:00 p.m. - 1:20 p.m.
Jane Breen, Ontario Tech University


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.


Fiedler Vectors with Unbalanced Sign Patterns

1:30 p.m. - 1:50 p.m.
Sooyeong Kim, University of Manitoba


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.


Spectral Properties of the Exponential Distance Matrix

2:00 p.m. - 2:20 p.m.
Kate Lorenzen, Linfield University


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.


Spectral Turán Problems

2:30 p.m. - 2:50 p.m.
Michael Tait, University of Villanova


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.


Quantum Walks on Graphs

3:00 p.m. - 3:20 p.m.
Sabrina Lato, University of Waterloo


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.


Addressing Graphs and Eigenvalues

3:30 p.m. - 3:50 p.m.
Sebastian Cioabă, University of Delaware


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.