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

Graphs and Combinatorial Geometry

DAVID HERSCOVICI, Quinnipiac University
Optimal Pebbling in Hypercubes using Error-correcting codes  [PDF]

A \emph{pebbling distribution} on a graph $G$ consists of placing pebbles on $V(G)$. A \emph{pebbling move} removes two pebbles from some vertex and adds one pebble to an adjacent vertex. A distribution is \emph{solvable} if a pebble can be moved to any target vertex by a sequence of pebbling moves. Using error-correcting codes, we construct solvable distributions on hypercubes $Q^n$ where the number of pebbles is in $O(1.34^n)$, improving on previously constructed distributions.

TONY NIXON, Lancaster University
Combinatorial Rigidity on Surfaces  [PDF]

Laman's theorem provides a characterisation of minimally rigid generic 2-dimensional (bar-joint) frameworks in purely combinatorial terms, while the corresponding characterisation in 3-dimensions remains a hard open problem. In this talk we will show that such characterisations are possible on frameworks constrained to certain 2-dimensional surfaces. The key step we will discuss is to provide inductive constructions of the classes of [2,l]-tight graphs (for l=1,2,3).

DAVID RICHTER, Western Michigan University
How to draw a 4-edge-colored graph  [PDF]

Define a ``parallel drawing'' of a $d$-edge-colored, $d$-regular graph a drawing in the plane such that (a) every vertex is represented by a point, (b) every edge is represented by a segment, and (c) the edges sharing a common color are parallel. The 3-edge-colored graphs which admit a faithful projective drawing were recently completely characterized. The purpose here is to explain the complications when one considers the corresponding problem for 4-edge-colored graphs.

JACOBUS SWARTS, Vancouver Island University
The $C_k$-extended Graft Construction  [PDF]

Gutjahr, Welzl and Woeginger found polynomial-time algorithms for a number of digraph homomorphism problems. These algorithms are based on the \underbar{$X$}-enumeration, the $C_k$-extended \underbar{$X$}-enumeration and the \underbar{$X$}-graft construction. In this talk, we show how the last two methods can be combined to obtain new polynomial-time algorithms, which also work for list homomorphisms. In the process, we are able to extend results of Bang-Jensen and Hell, dealing with homomorphisms to bipartite tournaments, to list homomorphisms.

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