Graphs and matrices
Responsable et prÃ©sident: Shaun Fallat et Karen Meagher (University of Regina)
[PDF]

WAYNE BARRETT, Brigham Young University
The Fielder Vector and Tree Decompositions of Graphs  [PDF]

In the 1970's Fiedler initiated a study of the second smallest eigenvalue of the Laplacian matrix $L$ of a graph and the corresponding eigenvector(s). These "Fiedler" vectors have become spectacularly successful in revealing properties of the associated graph. A tree decomposition $\cal T$ of a graph $G=(V,E)$ is an associated tree whose nodes are subsets of $V$ and whose edge set respects the structure of $G$. Tree decompositions have been used in the analysis of complex networks. This talk reports on an algorithm developed by students at BYU for obtaining a tree decomposition by means of Fiedler vector(s) of $G$.

JANE BREEN, University of Manitoba
Stationary vectors of stochastic matrices subject to combinatorial constraints  [PDF]

Given a strongly connected directed graph D, let SD denote the set of all stochastic matrices whose directed graph is a spanning subgraph of D. Can we describe the set of stationary vectors of irreducible members of SD? We will use results from the area of convex polytopes and an association of each matrix with an undirected bipartite graph to tackle this question, and discuss applications of this to the area of Markov chains, as well as some more unusual applications. This talk is based on joint work with Steve Kirkland.

KAREN MEAGHER, University of Regina
Graphs that have a weighted adjacency matrix with spectrum $\{\lambda_1^{n-2}, \lambda_2^2\}$  [PDF]

In this talk I will characterize the graphs which have an edge weighted adjacency matrix belonging to the class of $n \times n$ involutions with spectrum equal to $\{ \lambda_1^{n-2}, \lambda_2^{2} \}$ for some $\lambda_1$ and some $\lambda_2$. The connected graphs turn out to be the cographs constructed as the join of at least two unions of pairs of complete graphs, and possibly joined with one other complete graph.