2025 CMS Winter Meeting
Toronto, Dec 5 - 8, 2025
Algebraic Graph Theory: progress and problems
Org: Homer De Vera (University of Manitoba), Chris Godsil (University of Waterloo) and Hermie Monterde (University of Regina)
[PDF]
Org: Homer De Vera (University of Manitoba), Chris Godsil (University of Waterloo) and Hermie Monterde (University of Regina)
[PDF]
- JANE BREEN, Ontario Tech University
- STEVE BUTLER, Iowa State University
Cospectral constructions for the $q$-Laplacian matrix [PDF]
- STEVE BUTLER, Iowa State University
-
Given a graph we consider the q-Laplacian matrix described as $qD+A$ where $D$ is the diagonal matrix of degrees and $A$ is the adjacency matrix. By proper selection of $q$ we recover well known matrices ($q=0$ is the adjacency; $q=1$ is the signless Laplacian; $q=-1$ is, up to sign, the Laplacian).
It is known that there are graphs which are cospectral (same multiset of eigenvalues) for the $q$-Laplacian for arbitrary choice of $q$ (any regular cospectral pair suffices, but regularity is not needed). The goal of this talk is to highlight some pair of graphs which are cospectral for the $q$-Laplacian for only some specific values of $q$ and we show there are infinitely many values of which have a cospectral pair. One of our tools we will use is some generalization of Godsil-McKay switching.
- JOHN BYRNE, University of Delaware
- MICHAEL CAVERS, University of Toronto Scarborough
- ADA CHAN, York University
- HOMER DE VERA, University of Manitoba
- CHRIS GODSIL, University of Waterloo
- HIMANSHU GUPTA, University of Regina
- ZILIN JIANG, Arizona State University
- SOOYEONG KIM, University of Guelph
- STEVE KIRKLAND, University of Manitoba
An edge centrality measure based on Kemeny's constant [PDF]
- MICHAEL CAVERS, University of Toronto Scarborough
-
Given a connected graph $G$, Kemeny's constant $\kappa(G)$ is a parameter associated with the random walk on $G$ that measures how easily the random walker circulates through the vertices of $G$. We consider a measure of edge centrality $c(\bullet)$ that is based on Kemeny's constant. In the special case that $e$ is a cut edge of $G$ whose deletion yields the disconnected graph $G_1 \cup G_2,$ it turns out that $c(e)=\kappa(G)-\kappa(\widehat G_1)-\kappa(\widehat G_2),$ where $\widehat G_1$ (resp. $ \widehat G_2$) is formed from $G_1$ (resp. $ G_2$) by adding a loop at the vertex incident with $e$.
When $G$ is a tree, we produce a formula for $c(e)$ that is completely combinatorial. That formula yields attainable upper and lower bounds on $c(e)$ for trees, and facilitates an analysis of the behaviour of $c(e)$ when a branch of the tree is moved.
Joint work in progress with Max Wiebe.
- HITESH KUMAR, Simon Fraser University
- ALICE LACAZE-MASMONTEIL, University of Regina
On the second largest eigenvalue of certain graphs in the perfect matching association scheme [PDF]
- ALICE LACAZE-MASMONTEIL, University of Regina
-
Defined as the difference between its two largest eigenvalues, the spectral gap of a graph plays an important role on our understanding of its connectivity as observed by Godsil and Royle (2001). Since computing the largest eigenvalue of a graph is generally not too difficult, the crux to understanding the spectral gap of a graph is to compute its second largest eigenvalue. In this talk, we will consider the spectral gap of certain graphs in the perfect matching association scheme. Since these graphs are part of the same association scheme, they have the same eigenspaces. These eigenspaces correspond to irreducible representations of the symmetric group and thus, one could use these irreducible representations to compute the eigenvalues of each graph. In practice, such computations are difficult to perform which makes it difficult to find the eigenspace that realizes the second largest eigenvalue. The focus of my talk will be to identify this eigenspace for selected graphs in the scheme. This is joint work with Himanshu Gupta, Allen Herman, Roghayeh (Mitra) Maleki, and Karen Meagher.
- WILLIAM MARTIN, Worcester Polytechnic Institute
- BOBBY MIRAFTAB, Carleton University
- HERMIE MONTERDE, University of Regina
- JOY MORRIS, University of Lethbridge
A new measure of EKR-robustness on permutation groups [PDF]
- BOBBY MIRAFTAB, Carleton University
-
One of many questions that arises naturally out of extensions of the Erd\H{o}s-Ko-Rado Theorem, is the question of how many edges must be removed from a graph before the independence number increases. We study a variation on this question. The derangement graph of a permutation group is the Cayley graph on that group, whose connection set consists of all of the derangements in the group. Since we are dealing with Cayley graphs, rather than considering all subgraphs that can be produced by removing edges, we instead consider only subgraphs that are still Cayley graphs on the original group: that is, that can be produced by removing inverse-closed sets of elements (derangements) from the original connection set.
This is joint work with Karen Gunderson, Karen Meagher, Venkata Raghu Tej Pantangi, and Mahsa N. Shirazi.
- JOHNNA PARENTEAU, University of Regina
- SHIVARAM PRAGADA, Simon Fraser University
- MARIIA SOBCHUK, University of Waterloo
- TINO TAMON, Clarkson University
- JOHN URSCHEL, Massachusetts Institute of Technology
- MERI ZAIMI, Université de Montreal
- HARMONY ZHAN, Worcester Polytechnic Institute
- SHIVARAM PRAGADA, Simon Fraser University