Graph Theory
[PDF]

G. BULLINGTON, University of Wisconsin-Oshkosh USA
$\{1,4\}$-leaper tours on a rectangular chessboard  [PDF]

A $\{1, 4\}$-leaper on an $m \times n$ board is a generalized knight that moves one unit horizontally or vertically and four units in the perpendicular direction. That is, a $\{1, 4\}$-leaper moves from $(x, y)$ to $(x \pm 1, y \pm 4)$ or $(x \pm 4, y \pm 1)$ and we need to stay on the board. Criteria for some of the possible dimensions of the board which allow a closed tour will be given.

The Structure of Gamma Graphs  [PDF]

The gamma graph of a graph $G$ has vertices labelled by the minimum dominating sets of $G$, and edges formed by joining all pairs of vertices whose associated minimum dominating sets differ in exactly one element. The central question is: which graphs occur as the gamma graph of some graph? We explicitly construct a graph having an arbitrary prescribed set of minimum dominating sets. This simplifies the central question by showing that a graph occurs as the gamma graph of some graph if and only if its vertices can be labelled by sets of equal size so that the adjacency condition for gamma graphs holds. Many of the major results on gamma graphs arise as straightforward corollaries, often with shorter and simpler proofs. We obtain several new results, including the classification of all gamma graphs on at most six vertices. This is joint work with Samuel Simon and Jonathan Jedwab.

ROSALIND HOYTE, Monash University
Decomposing $\lambda K_v$ into stars  [PDF]

It is known exactly when the complete multigraph $\lambda K_v$ can be decomposed into $m$-stars (Yamamoto et al., 1975 and Tarsi, 1979). If $\lambda=1$ this result has been extended to decompositions of the complete graph into stars of arbitrary specified sizes $m_1,\dots,m_t$ (Lin and Shyu, 1996). It is natural to ask when $\lambda K_v$ can be decomposed into stars of arbitrary specified sizes. It turns out that this question doesn't admit an easy answer. In this talk we present some of our initial findings on this problem.

Joint work with Darryn Bryant and Daniel Horsley.

MÁRIA MACEKOVÁ, P. J. Šafárik University in Košice
Optimal unavoidable sets of types of 3-paths for plane graphs with minimum degree 2  [PDF]

A 3-path of type $(i,j,k)$ is a path $uvw$ on three vertices $u$, $v$, and $w$ such that the degree of $u$ (resp. $v$, resp. $w$) is at most $i$ (resp. $j$, resp. $k$).The elements $i,j,k$ are called parameters of the type. The set $S$ of types of paths is optimal unavoidable for a family $\cal{F}$ of graphs if each graph $G$ from $\cal{F}$ contains a path of the type from $S$, and neither any type can be omitted from $S$, nor any parameter of any type from $S$ can be decreased.

In the talk we present the unavoidable sets of types of 3-paths for the family of plane graphs having $\delta(G) \geq 2$ and $g(G) \geq 4$. For some values of girth we give two mutually uncomparable optimal unavoidable sets of types of 3-paths.

LAURA TESHIMA, University of Victoria
Variations on the $\gamma$-graph  [PDF]

Given the collection $S_1, S_2,\dots, S_n$ of minimum dominating sets of a graph $G$, the \emph{$\gamma$-graph} $G(\gamma)$ of $G$ has $V(G(\gamma))=\{v_1,v_2,\dots,v_n\}$ where $v_i \in V(G(\gamma))$ corresponds to the set $S_i$ in $G$, and $v_iv_j \in E(G(\gamma))$ if and only if there exist $u,w \in V(G)$ with $uw\in E(G)$, such that $S_i= (S_j-\{u\}) \cup \{w\}$. We present new variations on the $\gamma$-graph, including the $\gamma^{ID}$-graph and the $i$-graph, defined by the \emph{identifying code number} $\gamma^{ID}(G)$, and the \emph{independent domination number} $i(G)$, respectively. We examine some initial structural and existence results for these new classes.