COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2011

A set S ⊆ V is a dominating set of a graph G=(V,E) if every vertex in V-S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. In this talk we consider the family of all γ-sets in a graph G and we define the γ-graph G(γ)=(V(γ),E(γ)) of G to be the graph whose vertices V(γ) correspond 1-to-1 with the γ-sets of G, and two γ-sets, say D₁ and D₂, are adjacent in E(γ) if there exists a vertex v in D₁ and a vertex w in D₂ such that v is adjacent to w and D₁= D₂ - {w} ∪ {v}, or equivalently, D₂ = D₁ - {v} ∪ {w}. In this talk we initiate the study of γ-graphs of graphs. This is joint work with Gerd Fricke, Sandra M. Hedetniemi and Kevin R. Hutson.

Previous Talks

A latin square of order n is an n by n array of n symbols in which each symbol occurs exactly once in each row and column. A transversal of such a square is a set of n entries containing no pair of entries that share the same row, column or symbol. For example, here is a transversal in a latin square of order 4:

Don't worry about wearing a smock- we won't be painting. No previous knowledge of graph colouring will be assumed. We will start with a quick introduction to colouring graphs, and increase the conditions on colourings until we arrive at reflexive injective oriented colouring, or rio-colouring for short. Then we will show the problem of answering whether an oriented graph is k-rio-colourable becomes NP-complete for values of k >= 3. The complexity proof of this problem exposes a delicate structure result which we have called the Neighbour-juggling Graph. Because the decision problem is polynomial-time solvable for k=2, we present the characterization of graphs that are 2-rio-colourable. From there, we discuss rio-cliques, and their implication on bounds for the rio-chromatic number, which can be improved when restricting ourselves to oriented trees. Finally, we present an efficient algorithm for colouring oriented trees. Be inspired to take a riverboat ride down the Rio-Grande afterwards as a self-reward for learning a new way of colouring graphs.

A Latin square of order n is a n x n array of n symbols such that each symbol appears exactly once in each row and exactly once in each column. Two Latin squares of order n are orthogonal if when superimposed, each ordered pair of symbols occurs exactly once. One of the big unsolved problems in design theory is to determine if it is possible to find three pairwise orthogonal Latin squares of order 10. A pair of mutually orthogonal Latin squares (MOLS) of order 10 can be represented as a binary matrix whose dimension can be computed modulo two. We generated all pairs of MOLS of order 10 with dimension 35 or less and concluded that if there is a triple of MOLS of order 10 then each pair of MOLS in the triple corresponds to an array of dimension 36 or 37. The search determined that no pairs of dimension 33 or less exist and that only 6 pairs of MOLS (up to main class equivalence) have dimension 34 (these are counterexamples to a conjecture of Moorhouse).

This is joint work with Erin Delisle (Univ. of Toronto) and Leah Howard (Univ. of Victoria).

The classic De Bruijn cycle is a cyclic string of length 2ⁿ that contains every bitstring of length n as a substring exactly once. We show how to efficiently construct a cyclic string of length (n choose k) which contains every substring of length n-1 with density k or k-1 exactly once. On average, the algorithm generates each bit of the string in constant time and is based on a new algorithm for generating necklaces (binary strings under rotation) in cool-lex order, a Gray code variant of colex order.

This is joint work with Joe Sawada (Guelph University) and Aaron Williams (Carleton University).