Page > 1 > 2 > 3 > 4

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:

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:

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

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

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:

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 OR David Wood email

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:

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:

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:

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:

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:

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

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:

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 :

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

Page > 1 > 2 > 3 > 4