**Anti-Ramsey Theory for cycles in Complete Graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Kyle Pula

**Institution: **University of Denver

**Date: **20/04/2010 2:15pm

**Abstract: **This talk will survey results in anti-ramsey theory for
cycles. Specifically, we'll look at edge-colorings of complete finite graphs that lack rainbow cycles of prescribed lengths. (A subgraph is rainbow if its edge-colors are pairwise distinct.) The talk will be a
gentle survey of results in this area with no particular background required.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Thrackles and related graph drawings**

*Discrete Structures and Algorithms (Seminar)*

**by **Grant Cairns

**Institution: **La Trobe University

**Date: **13/04/2010 2:15pm

**Abstract: **A thrackle is a drawing of a finite graph in which every pair
of edges meet exactly once, either at a common vertex or at a transverse
crossing. The pentagram is a simple example. This talk outlines joint
work with Yury Nikolayevsky in which we use homologocal ideas to
examine Conway's thrackle conjecture.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Load balancing and random graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Professor Nick Wormald

**Institution: **Department of Combinatorics and Optimization, Waterloo University, Canada

**Date: **30/03/2010 2:15pm

**Abstract: **A general problem area involves job assignments. There is a set of
jobs to be assigned to processors (i.e. things that can deal with the
jobs). We wish to assign the jobs such that, roughly speaking, all
processors are kept as busy as possible. Various problems arise by
imposing different constraints and objective functions can be
imposed. I will discuss some of these, and in particular, a connection
to a problem concerning orientations of graphs or hypergraphs.
Thus, when can a graph's edges be oriented so that the maximum
indegree is at most k? How can we find such an orientation quickly?
This setting gives rise to problems on thresholds, and algorithms, for
random graphs and hypergraphs. The talk will include some recent
work with Jane Gao.

*For more information: *contact: David Wood. email woodd@unimelb.edu.au

**Hadwiger's Graph Colouring Conjecture**

*Discrete Structures and Algorithms (Seminar)*

**by **Dr David Wood

**Institution: **Mathematics and Statistics, The University of Melbourne

**Date: **16/03/2010 2:15pm

**Abstract: **Hadwiger's Conjecture is a sweeping generalisation of the
four-colour theorem for planar graphs, and is widely considered to be
one of the most important open problems in combinatorics. It states
that every graph containing no complete graph of order t as a minor
is (t-1)-colourable. The case t=5 implies the four-colour theorem.
The conjecture is known to be true for t <= 6, but is wide open for large t.
This talk will introduce graph colourings, graph minors, and Hadwiger's
Conjecture. I will conclude with some recent progress on a weakening of
Hadwiger's Conjecture that employs list colourings, some graph structure
theory, and a new sufficient condition for a graph to have a set of edges
whose contraction increases the connectivity.

*For more information: *contact: Dr David Wood. email woodd@unimelb.edu.au

**The Degree-Diameter Problem: A Few Results and a Wealth of Open Problems**

*Discrete Structures and Algorithms (Seminar)*

**by **Guillermo Pineda-Villavicencio, University of Ballarat

**Institution: **Mathematics and Statistics

**Date: **12/03/2010 1:00pm

**Abstract: **The Degree-Diameter Problem asks for the largest graph with given maximum degree and diameter. In joint work with Eyal Loz (University of Auckland) and Hebert Perez-Roses (The University of Newcastle), we have recently constructed the largest known graphs of maximum degree in [17,20] and diameter in [2,10]. A wide range of techniques and concepts were used, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. Among the techniques employed, we believe voltage graphs are the leading beacon for future directions in the construction of large graphs. However, many weaknesses need to be tackled to reach their potential. For instance,
(i) There is no methodology to obtain voltage groups and voltage assignments to generate graphs with specific properties.
(ii) The procedure is done "blindly" in the sense that little is known about the classes of graphs that can be lifted.
In this talk we present a number of ideas and open problems that address these defects.

*For more information: *For more information contact Dr. David Wood: woodd@unimelb.edu.au

**Cores of vertex-transitive graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Ricky Rotheram

**Institution: **Department of Mathematics and Statistics, The University of Melbourne

**Date: **02/03/2010 1:15pm

**Abstract: **A homomorphism of two graphs X and Y is a map between the vertex sets V(X) and V(Y) such that f(x) is adjacent to f(y) in Y whenever x and y are adjacent in X. Examples include automorphisms, isomorphisms and retractions, which are homomorphisms from a graph to one of its induced subgraphs (known as a retract). In this talk I will outline my proposed research project, which is to investigate the cores (minimal retracts) of some families of cayley graphs, and will summarise the existing results for the cores of vertex-transitive graphs.

*For more information: *contact Sanming Zhou email sanming@unimelb.edu.au OR David Wood email woodd@unimelb.edu.au

**Characterizations and algorithms for topological containment of wheel graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Rebecca Robinson

**Institution: **Monash University

**Date: **15/09/2009 2:15pm

**Abstract: **Topological containment is an important substructure relation in graph theory. A graph G is
said to topologically contain another pattern graph H if a graph isomorphic to H can be
obtained from G by performing a series of deletions and contractions, where contractions are
limited to edges with at least one endvertex of degree 2.
The problem of topological containment has been shown by Robertson and Seymour to be
polynomial-time solvable for any fixed pattern graph. However, practical characterizations
and algorithms have only been developed for a few small pattern graphs. In this talk, I will
look at some previous results on topological containment for particular pattern graphs. I will
also talk about two new results: one characterizing graphs that do not topologically contain
the wheel with six spokes, and one that gives a characterization (up to bounded size pieces)
of graphs that do not topologically contain the wheel with seven spokes.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**A combinatorial approach to Tutte polynomial inequalities**

*Discrete Structures and Algorithms (Seminar)*

**by **Arun P Mani

**Institution: **Monash University

**Date: **08/09/2009 2:15pm

**Abstract: **The Tutte polynomial of a connected graph (and more generally, a
matroid) is a two-variable polynomial known to encode a wide variety
of combinatorially interesting information of the graph, including the
number of subgraphs that are acyclic (forests), number of spanning
trees and the number of subgraphs that are connected. This polynomial
can be defined using a non-negative integer function, the rank
function, r, which is defined on the subsets of the edge set of the
graph. A fundamental property of the rank function is its
submodularity. That is, for subsets A, B of E(G), r(A union B) +
r(A intersection B) <= r(A) + r(B).
In this talk, I'll define a property for graphs (and matroids) that
extends rank submodularity in a way that can be applied to prove some
inequalities for its Tutte polynomial in the positive quadrant. This
region includes all three of the above mentioned counting problems.
I'll then talk about what is known about the existence of this
extended submodular property in graphs and matroids. I'll finally
demonstrate with some simple examples how to apply all of this to get
some non-trivial bounds for Tutte polynomial evaluations in the
positive quadrant.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Rook polynomials, matchings and permanents**

*Discrete Structures and Algorithms (Seminar)*

**by **Ian Wanless

**Institution: **School of Mathematical Sciences, Monash University

**Date: **01/09/2009 2:15pm

**Abstract: **Let $m_i(G)$ be the number of matchings of size $i$ in a graph $G$. I will look at some results and open problems motivated by variants of my core goal of trying to maximise $m_n(G)$ among $k$-regular bipartite graphs on $2n$ vertices. The key tools will be
The rook polynomial of $G$, defined by
\rho(G)=\sum_{i=0}^n(-1)^i m_i(G)x^{n-i}.
The permanent of a square matrix $A=[a_{ij}]$, given by
per(A)=\sum_\tau\prod_{i=1}^n a_{i\tau(i)},
where the sum is over all permutations of $\{1,2,\dots,n\}$.
Generating functions that count certain walks in $G$ and thereby produce formulae for $m_i$ in terms of counts of small subgraphs of $G$.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Optimization Problems: Duality and Computational Models**

*Discrete Structures and Algorithms (Seminar)*

**by **Prabhu Manyem

**Institution: **University of Ballarat & Shanghai University

**Date: **11/08/2009 2:15pm

**Abstract: **In this talk, we will show a method by which optimization
problems can be solved by a single call to a "decision" Turing machine,
as opposed to multiple calls using a classical binary search setting.
We will use concepts from duality and descriptive complexity
(which is based on second order Logic).

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**How to use the Lovasz Local Lemma**

*Discrete Structures and Algorithms (Seminar)*

**by **David Wood

**Institution: **The University of Melbourne, Department of Mathematics and Statistics

**Date: **04/08/2009 2:15pm

**Abstract: **The LovÃ¡sz Local Lemma is a powerful probabilistic tool for proving the existence of combinatorial objects.
In this informal talk I will explain the various versions of the LovÃ¡sz Local Lemma, and illustrate how to use them by proving a number of theorems about graph colouring. No background in probability or graph theory will be assumed.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**Imprimitive symmetric graphs with cyclic blocks**

*Discrete Structures and Algorithms (Seminar)*

**by **Sanming Zhou

**Institution: **The University of Melbourne, Mathematics and Statistics Department

**Date: **21/07/2009 2:15pm

**Abstract: **This talk is based on a joint paper with Cai Heng Li and Cheryl Praeger. A graph X is symmetric if its automorphism group Aut(X) is transitive on the set of arcs (oriented edges) of X.
If a subgroup G of Aut(X) acts transitively on the set of arcs of X and leaves invariant a nontrivial partition of the vertex set, then X is called an imprimitive G-symmetric graph. We study such graphs satisfying the following conditions: for two parts B, C of the partition, either there is no edge of X between B and C, or exactly two vertices of B lie on no edge with a vertex of C; and as C runs over all parts adjacent to B these vertex pairs (ignoring
multiplicities) form a cycle. We prove that this occurs if and only if the size of each part of the partition is 3 or 4, and moreover we give constructions of three infinite families of such graphs. I will also mention recent progress on a problem arising from our results.

*For more information: *contact: David Wood. email woodd@unimelb.edu.au

**Two domination parameters in graphs**

*Discrete Structures and Algorithms (Seminar)*

**by **Guangjun Xu

**Institution: **Mathematics and Statistics Dept, The University of Melbourne

**Date: **30/06/2009 2:15pm

**Abstract: **Let $G$ be a graph. A subset $S$ of $G$ is called a dominating set if every vertex not in $S$ has a neighbour in $S$. The cardinality of a minimum dominating set of $G$ is called the domination number of $G$. In this talk, I will introduce the concepts of power domination and $k$-rainbow domination in graphs.
Power domination arises from the power network monitoring problem, which seeks to place as few phase measurement units (PMUs) as possible at selected network locations such that the whole network can be monitored. I will present our results of power domination in block graphs.
Assume we have a set of $k$ colours and we assign an arbitrary subset of these colours to each vertex of a graph $G$. If we require that each vertex to which an empty set is assigned has in its neighborhood all $k$ colours, then this assignment is called a $k$-rainbow dominating function of $G $.
I will address the $2$-rainbow domination in the generalized Petersen graphs.
Joint work with L. Kang, E. Shan and M. Zhao.

*For more information: *contact: David Wood. email: woodd@unimelb.edu.au

**An Efficient Algorithm for Partial Order Production**

*Discrete Structures and Algorithms (Seminar)*

**by **Gwenael Joret

**Institution: **Departement d'Informatique, Universite Libre de Bruxelles

**Date: **16/06/2009 2:15pm

**Abstract: **We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the worst case. Here, n denotes the size of the ground sets, and ITLB denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target poset. The overall complexity of our algorithm is polynomial. This answers a question of Yao (SICOMP, 1989). A key ingredient in our analysis is the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound. Joint work with J. Cardinal, S. Fiorini, R. M. Jungers, and I. Munro.

*For more information: *contact: David Wood, email : woodd@unimelb.edu.au

**Why Study the Crossing Number of a Graph?**

*Discrete Structures and Algorithms (Seminar)*

**by **David Wood

**Institution: **The University of Melbourne

**Date: **09/06/2009 2:15pm

**Abstract: **The crossing number of a given graph is the minimum number of crossings in a drawing of that graph. This seminar will be a broad introduction to this topic, aimed at an audience with little or no background in graph theory. I will describe the history of the crossing number, applications of the crossing number to other areas of mathematics, such as combinatorial geometry (the Szemeredi- Trotter theorem) and combinatorial number theory (sum-sets and product- sets), as well as applications in computer science (network visualisation). I will conclude the talk by discussing my own research that establishes connections between the crossing number and structural graph theory (graph minors).

*For more information: *David Wood email woodd@unimelb.edu.au