CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Algebraic Graph Theory

SATYANARAYANA REDDY ARIKATLA, Indian Institute of Technology Kanpur, Kanpur, India
Relationships among some graph algebras on some graph classes  [PDF]

Let $X$ be a graph with $n$ vertices and $A$ be the adjacency matrix of $X$. By a graph algebra of $X$, we mean a matrix subalgebra of $M_n(\mathbb{C})$ which contains $A$, where $\mathbb{C}$ is the field of complex numbers. In this study we explore the relationships among the following four graph algebras of a graph $X$ for several graph classes.

a) adjacency algebra b) commutant algebra c) coherent closure and d) centralizer algebra.

DANIELLE COX, Dalhousie University
Roots of Graph Polynomials  [PDF]

As R.C. Rota said, ``...all sorts of problems of combinatorics can be viewed as problems of location of the zeros of certain polynomials and in giving these zeros a combinatorial interpretation''. In this talk we will discuss new and old approaches for investigating the roots of graph polynomials. We will discuss the nature and location of the roots of network reliability polynomials, vertex cover polynomials and chromatic polynomials, among others.

ELISSA ROSS, York University
Finite motions from periodic frameworks with additional symmetry  [PDF]

Many crystal-like materials exhibit periodic structure with additional symmetry within their periodic cells. The flexibility of these materials may determine their physical properties, motivating the development of new counting rules for predicting the flexibility of crystallographic frameworks. We study such a symmetric periodic framework through its orbit graph, a finite digraph whose edges are labeled by elements of the symmetry group $\mathbb Z^3 \rtimes \mathcal S$, where $S$ is a crystallographic point group.

ROBERT ŠÁMAL, Charles University
Highly arc transitive digraphs  [PDF]

We resolve two questions by Cameron, Praeger, and Wormald [Combinatorica 1993] on highly arc-transitive digraphs (shortly, hats). Hat is an infinite digraph that is $s$-arc-transitive for every $s$.

We construct a hat with universal reachability relation for all possible degrees that were not ruled out by results of Praeger and Malnic. Second, we disprove a conjecture concerning structure of two-ended hats and provide an approach towards characterizing these graphs. (joint with B.Mohar and M.DeVos)

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria