Stacks, queues, deques and their representation as graphsFranz BrandenburgUniversity of Passau, Germany 10:00 Wednesday 25th January 2012 Room 215 Richard Berry Stacks and queues are fundamental data structures. They express the LIFO (last-in, first out) and FIFO (first-in, first-out) principles and are the basis for depth first and breadth first search. Stacks and queues are a specialization of a deque, which allows the insertion and removal of objects on its left and right ends. In Java 6 the class Arraydeque implements a deque and is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. We consider classes of graphs which represent the input-ouput behaviour of these data structures, and call them stack, queue, or deque graphs. Then the input-output actions on a stack are correct if and only if the stack graph is planer. Accordingly, queue graphs have a planar representation on a cylinder and the deque graphs are characterized by planar graphs on the cylinder with additional arches. Hence, we can state: correct if and only if planar. We study properties of the classes of stack, queue and deque graphs, which are subclasses of planar graphs. By Yannakakis result every planar graphs can be represented by four stacks. In particular, one stack graphs are two queue graphs, and one queue graphs are two stack graphs. Our latest result states that in terms of graphs a deque dominates two stacks exactly by the difference between a Hamilton cycle and a Hamilton path in planar graphs. We close with challenging open problems that are related to stacks and queues. |
Vertices of high degree in the preferential attachment treeGraham BrightwellLondon School of Economics, UK 11:00 Tuesday 15th November 2011 Russell Love Theatre Richard Berry The preferential attachment tree is the most basic model of evolving web graphs and social networks. At each stage of the process, a new vertex is added and joined to one of the existing vertices, with each vertex chosen with probability proportional to its current degree. In probability theory, this is also known as a Yule process. Much is known about this model, including the fact that the numbers of vertices of each small degree follow a ``power law''. Here we study in detail the degree sequence of the preferential attachment tree, looking at the vertices of large degrees as well as the numbers of vertices of each fixed degree. This is joint work with Malwina Luczak. |
Albertson's conjecture and 5-coloring non-planar graphsJanos BaratMonash University 11:00 Tuesday 8th November 2011 Russell Love Theatre Richard Berry A graph is planar, if it can be drawn in the plane without edge crossings. It follows from the Euler-formula, that any planar graph has a vertex of degree at most 5. Therefore, using a greedy coloring algorithm, we can trivially color the vertices of a planar graph by 6 colors. It is still easy to prove that 5 colors suffice. What happens if we allow some edge crossings in the drawing? Can we still 5 color the vertices? Is there any connection between the minimum number of crossings in a drawing of a graph G and its chromatic number? Both of these graph parameters are hard to compute. Still, Mike Albertson formulated a conjecture in 2007 that for any r-chromatic G, the crossing number of G is at least the crossing number of $K_r$, the complete graph on $r$ vertices. This conjecture is a weakening of Hajos conjecture, and it includes the 4 color theorem as a subcase. We will show that this conjecture follows from some known results up to a factor of 4. It is also true for r at most 16, despite the fact that we only know the crossing number of $K_r$ for $r$ at most 12. |
First-Fit chain partitioning of partial ordersGwenaël JoretUniversité Libre de Bruxelles Belgium 11:00 Tuesday 25th October 2011 Russell Love Theatre Richard Berry By Dilworth's theorem, every partial order P can be partitioned into w chains, where w is the maximum size of an antichain in P (called the width of P). A natural greedy algorithm to construct a chain partition of P with few chains is First-Fit: Consider the elements of P in some order and put each element v in the first chain that fits, that is, the first chain C where v is comparable to all elements in C. It has been known for a long time that First-Fit uses O(w) chains on interval orders of width w, and it was conjectured that this remains true more generally for partial orders without two incomparable chains of length k, for fixed k (for k=2, these are exactly the interval orders). In this talk I will present a proof of this conjecture. This is joint work with Kevin G. Milans (U. South Carolina). |
Untangling planar graphsVida DujmovićCarleton University Ottawa, Canada 11:00 Tuesday 18th October 2011 Russell Love Theatre Richard Berry Problems involving reconfigurations of geometric objects appear in all areas of science and engineering. Motivated by applications in gaming, we study reconfigurations of geometric graphs (that is, straight-line drawings of graphs with possibly lots of edge crossings). To untangle a geometric planar graph means to move some of its vertices so that the resulting geometric graph has no crossings. A popular on-line game, called, Planarity, asks a player to untangle a given geometric planar graph. The problem has also been studied in mathematical circles. We answer an open problem by Pach and Tardos [Discrete Comput. Geom., 2002] by providing the first polynomial lower bound for untangling geometric planar graphs. |
Small graph minorsDavid WoodDepartment of Mathematics and Statistics The University of Melbourne 11:00 Tuesday 13th September 2011 Russell Love Theatre Richard Berry A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is "small" with respect to the order of the whole graph. Other related results will be explored. Joint work with Samuel Fiorini, Gwenael Joret, and Dirk Theis. |
Wide containers in Gaussian networksMuhammad SuraniDepartment of Mathematics and Statistics The University of Melbourne 11:00 Tuesday 6th September 2011 Russell Love Theatre Richard Berry A Gaussian network is a Cayley graph modelled on a quotient ring of the Gaussian integers. Indeed, many circulant graphs and tori are isomorphic to Gaussian networks, and so this provides a useful algebraic structure with which to study them. Many highly sought after properties in interconnection networks and coding theory (e.g. diameter, shortest paths) can be easily obtained under this framework. The concept of wide containers will also be introduced to unify the properties of connectivity and diameter. |
Linear and cyclic metric labelling problems for complete m-ary treesKelvin Yang LiDepartment of Mathematics and Statistics The University of Melbourne 11:00 Tuesday 16th August 2011 Russell Love Theatre Richard Berry The frequency assignment problem is concerned with assigning frequency to each transmitter such that the maximum span of the frequency is minimized under some distance constraints. In reality the closer two transmitters are, the larger the separation between their frequencies are required to be. Such problems can be turned into graph labelling problems. Given a positive integer h, an L(h,1,1)-labelling of a graph is an assignment of non-negative integers to its vertices such that adjacent vertices receive labels differing by at least h and vertices with distance 1 or 2 apart receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used. The objective is to find the minimum span over all L(h,1,1)-labellings. In this talk we will discuss recent results on the L(h,1,1)-labelling problem and its cyclic version for complete m-ary trees. |
A construction of imprimitive symmetric graphsBin JiaDepartment of Mathematics and Statistics The University of Melbourne 16:15 Monday 30th May 2011 Hercus Theatre (L105, floor 1) David Caro Building (Physics) Let G be a finite simple graph without isolated vertices. An automorphism of G is a permutation of its vertices that preserves the adjacency and non-adjacency relations. G is called symmetric if any arc (ordered pair of adjacent vertices) can be mapped to any other arc by some automorphism. G is imprimitive with respect to an arc-transitive subgroup of its automorphism group if its vertex set admits a non-trivial partition P that is invariant under the action of the subgroup. In this case the quotient graph is defined to have vertex set P such that two blocks are adjacent if and only if an edge of G between them exists. For any two adjacent blocks of P, if not all vertices of one block have neighbours in the other, then G is not a multicover of the quotient graph. In this case we give a combinatorial method for reconstructing the imprimitive graph from certain natural local structures of its quotient. This talk is aimed at a general audience. We will display most of ideas and results by pictures. The talk is based on joint work with Lu and Wang. |
Unitary graphs, and classification of a family of symmetric graphs with complete quotientsSanming ZhouDepartment of Mathematics and Statistics The University of Melbourne 16:15 Monday 23rd May 2011 Hercus Theatre (L105, floor 1) David Caro Building (Physics) A finite graph is called symmetric if its automorphism group is transitive on the set of arcs (ordered pairs of adjacent vertices) of the graph. This is to say that all arcs have the same status in the graph. I will talk about a family of symmetric graphs, called the unitary graphs, whose vertices are flags of the Hermitian unital (a special block design) and whose adjacency relations are determined by certain elements of the underlying finite fields. Such graphs admit the unitary groups as groups of automorphisms, and they play a significant role in our classification of a family of symmetric graphs with complete quotients. I will also talk about this classification and some combinatorial properties of the unitary graphs. This talk is based on joint work with M. Giulietti, S. Marcugini and F. Pambianco. |
On Anti-Collusion Codes and
Ying Miao |
Constraint Satisfaction Problems and Universal AlgebraMarcel JacksonSchool of Engineering and Mathematical Sciences La Trobe University, Melbourne 16:15 Monday 7th March 2011 Hercus Theatre (L105, floor 1) David Caro Building (Physics) It is well known that the task of deciding whether or not a finite graph is 2-colourable is rather easy, while the task of deciding whether or not a finite graph is 3-colourable is a familiar NP-complete problem. These problems fall into the general class of computational problems that ask for the existence of a function from some given combinatorial object (the vertices of the graph to be coloured) into some fixed domain (the colours) subject to preservation of certain given constraints (adjacent vertices are coloured differently). In other words, they are constraint satisfaction problems. A very large number of natural computational problems can be interpreted as constraint satisfaction problems, and classifying the computational complexity of CSPs has received quite intense attention over the past decade. Each CSP (with fixed target domain) is solvable in the class NP, but a very influential conjecture of Feder and Vardi is that a dichotomy holds: such a problem is either NP-complete or is solvable in polynomial time. This talk will be aimed at a general audience: we introduce the basic notions and the practical and theoretical motivations for studying the complexity of CSPs, with a particular focus on introducing the techniques from universal algebra that have informed most recent progress on the dichotomy conjecture. |
Genetic Algorithms and Configurations of PointsRuy Fabila-MonroyDepartamento de Matematicas Cinvestav, Mexico 16:15 Monday 28th February 2011 Hercus Theatre (L105, floor 1) David Caro Building (Physics) Let S be a set of n points in general position in the plane (no three on a line). Many problems in combinatorial geometry deal with counting the number of certain geometric configurations in S. For example, if we draw all the line segments joining pair of points, how many of them will cross? Of course this number will vary depending on the actual choice of S. So normally lower and upper bounds are sought. A part of this process involves searching for sets of points achieving (or being close as possible) to these bounds. For example, searching for the set that minimizes the number of crossings in the above problem. This is in general a difficult task. Few techniques are known and in many cases there is a big gap between the theoretical bound and the best example. In this presentation, I will talk about how I have been using genetic algorithms to search for these extreme examples and the results obtained so far. |
Algorithmic RandomnessRod DowneySchool of Mathematics, Statistics and Operations Research Victoria University of Wellington 14:15 Monday 7th February 2011 Russell Love Theatre, Richard Berry Building A sequence like 000000000000000000 does not seem random whereas one obtained by coin tosses does. An elementary fact from statistics says that both of the sequences would be equally likely. Algorithmic randomness seeks to reconcile these two facts and give meaning to questions like: What does it mean for a real or string to be random? What does it mean for an individual sequence to be partially random? Does randomness give more or less computational power? We survey recent work in this area. The talk will be aimed at a general audience, and no knowledge of logic or statistics is assumed. It will be aimed at advanced undergraduates or beginning graduate students. |
Colouring Circular Arc GraphsDaniel HarveyDepartment of Mathematics & Statistics University of Melbourne 11:00 Friday 4th February 2011 Room 215, Richard Berry Building Circular arc graphs are a class of graphs that can be represented by a set of arcs on a circle. Colouring problems on circular arc graphs can be used to model job allocation and certain problems in optical ring networks. Our goal is to solve a series of colouring problems for the class of circular arc graphs, including the Double Critical Graph Conjecture, the more general Erdos-Lovasz Tihany Conjecture, and Hadwiger's conjecture. We choose to consider this class of graphs as they are chi-bounded without being perfect. Thus the above graph colouring problems are interesting, nontrivial, and achievable. |
Problems in Geometric Graph TheoryMichael PayneDepartment of Mathematics & Statistics University of Melbourne 15:00 Tuesday 25th January 2011 Room 215, Richard Berry Building Geometric Graph Theory deals with classes of graphs that arise from various geometric settings. During my first year of candidature I have addressed problems involving two such classes. The first is that of colouring great circle arrangement graphs. These graphs have the crossing points of a set of great circles as vertices and the arcs as edges. Since they are planar graphs they are 4-colourable, but it is conjectured that three colours suffice. The second problem involves the visibility graphs of point sets in the plane. Two points in the set are joined by an edge if no other point lies on the straight line segment between them. I have investigated the question of whether visibility graphs with a fixed clique number (c) have bounded chromatic number. The answer is known to be yes for c=3 and no for c=6. I have studied the first remaining case, c=4. |
Some new results on the degree-diameter and the degree-girth problems, both asymptotic and non-existentialGuillermo Pineda-VillavicencioUniversity of Ballarat 14:00 Thursday 26th August 2010 Old Geology Theatre 1 The degree-diameter problem aims to find the largest possible order of a graph with given degree and diameter, while the degree-girth problem aims to find the smallest possible order of a graph with given degree and girth. In this context the Moore bound constitutes both an upper bound on the order of a graph of given maximum degree and diameter, and a lower bound on the order of a graph of given minimum degree and odd girth. Graphs missing or exceeding the Moore bound by e are called graphs with defect or excess e, respectively. With the exception of the degree 57 and diameter 2, Moore graphs have been fully characterized, so have been the graphs with defect or excess 1. However, graphs with defect or excess 2 represent a wide unexplored area. In the talk I present both asymptotic and non-existentence results on the class of graphs with defect or excess 2. Joint work with Charles Delorme (Universite Paris-Sud) |
Some wonderful conjectures (but almost no theorems) at the boundary between analysis, combinatorics and probabilityAlan SokalUniversity College London New York University 10:00 Thursday, 29th July 2010 Old Geology Theatre 1 I discuss some analytic and combinatorial properties of the entire function $F(x,y) = \sum\limits_{n=0}^\infty \frac{x^n}{n!} y^{n(n-1)/2}$. This function (or formal power series) arises in numerous problems in enumerative combinatorics, notably in the enumeration of connected graphs. |
Optimal gossiping protocol in the Gaussian and Eisenstein-Jacobi networksPongphat TaptagapornDepartment of Mathematics and Statistics The University of Melbourne 14:00 Thursday, 29th July 2010 Old Geology Theatre 1 The Gaussian and Eisenstein-Jacobi (EJ for short) networks are graphs induced by the Gaussian and EJ integers respectively. We look at communication protocols in these graphs, and here we focus on gossiping; where every vertices send a distinct message to all the other vertices in the graph. We will find the exact values of the gossip time and show that they are optimal under the store-and-forward, all-port and full-duplex model for gossiping. We will also look at the edge and arc-forwarding indices in all-to-all routing. Studies of these graphs were previously motivated by coding theory as they were known to generate "perfect" codes. More recently we have found that these graphs exhibit close connections to first-kind Frobenius graphs, circulant graphs and tori. |
Gossiping and routing in second-kind Frobenius graphsSanming ZhouDepartment of Mathematics and Statistics The University of Melbourne 2:15pm Tuesday 25th May 2010 Room 215, Richard Berry Building Two kinds of Cayley graphs associated with finite Frobenius groups exhibit interesting routing properties, making them attractive candidates (at least in theory) for modelling interconnection networks. In this talk I will focus on gossiping and routing in second-kind Frobenius graphs. In the case when the kernel of the Frobenius group involved is abelian of odd order, we find the exact value of the minimum gossiping time for such a graph under the store-and-forward, all-port and full-duplex model and prove that the graph admits optimal gossiping schemes with the following properties: messages are always transmitted along shortest paths; each arc is used exactly once at each time step; at each step after the initial one the arcs carrying the message originated from a given vertex form a perfect matching. In the case when the kernel of the Frobenius group is abelian of even order, we give an upper bound on the minimum gossiping time under the same model. As examples we will discuss a family of second-kind Frobenius graphs which contains all Paley graphs and connected generalized Paley graphs. This talk is based on joint work with Xin Gui Fang at Peking University. |
Cayley Graphs, Finite State Automata and Group AutomataAndrei KelarevSchool of Information Technology and Mathematical Sciences University of Ballarat 2:15pm Tuesday 18th May 2010 Room 215, Richard Berry Building Cayley graphs are closely related to the concepts of finite state automata and group automata. In particular, finite state automata are generalisations of the Cayley graphs, since every Cayley graph can be regarded as a finite state automaton. Group automata form an important subclass of the class of all finite state automata. On the other hand, Cayley graphs are capable of accomplishing all tasks performed by the finite state automata. These relations lead to new open questions concerning the influence of the theoretical properties of the Cayley graphs on their possible applications in directions where finite state automata have been used, including such areas as bioinformatics, data mining, computer graphics, and internet security. |
The many formulae that count Latin squaresDouglas S. StonesMonash University 2:15pm Tuesday 11th May 2010 Room 215, Richard Berry Building A Latin square is an $n \times n$ matrix containing $n$ distinct symbols such that each row and each column contains each symbol exactly once. Latin squares are widely used for designing experiments and in error-correcting codes. However, merely counting Latin squares poses a significant problem and many prior attempts have subsequently been proved faulty. Despite some claims to the contrary, there are many formulae for the number of Latin squares. In this talk, we will give a survey of these formulae and their history which stretches all the way back to MacMahon in 1898! |
Colouring the PlaneMichael PayneDepartment of Mathematics and Statistics University of Melbourne 2:15pm Tuesday 4th May 2010 Room 215, Richard Berry Building The Chromatic Number of the Plane problems asks for the least number of colours required to colour the plane so that points distance one apart receive different colours. Created in 1950, the problem has resisted all attempts to improve on the initial bounds (between 4 and 7) found soon afterwards. Of course, faced with such resistance mathematicians have studied many variations on the problem and found some interesting results. I will talk about some such variations, namely the study of measurable colourings, graphs whose measurable and general chromatic numbers differ, colourings of large subgraphs of the plane, and perhaps more if time permits. |
Chromatic factorisation and Galois groups of chromatic polynomialsKerri MorganClayton School of Information Technology Monash University 2:15pm Tuesday 27th April 2010 Room 215, Richard Berry Building The chromatic polynomial P(G,k) gives the number of proper k-colourings of a graph G. This polynomial is also studied in statistical mechanics where the limit points of the zeros give possible locations of physical phase transitions. We say P(G,k) has a chromatic factorisation, if P(G,k)=P(H1,k)P(H2,k)/P(Kr,k) for some graphs H1 and H2 and some r >= 0. Any clique-separable graph, that is, a graph that can be obtained by identifying an r-clique in H1 with an r-clique in H2, has a chromatic factorisation. A graph is said to be strongly non-clique-separable if it is neither clique-separable nor chromatically equivalent to any clique-separable graph. We identified strongly non-clique-separable graphs that have chromatic factorisations. We give an overview of some of our results on these chromatic factorisations including giving an infinite family of strongly non-clique-separable graphs that have chromatic factorisations. We then give a summary of the Galois groups of chromatic polynomials of degree at most 10. We are interested in identifying the relationships between graphs that have chromatic polynomials with the same Galois group. We give some families of graphs that have chromatic polynomials with the same Galois group. |
Anti-Ramsey Theory for Cycles in Complete GraphsKyle PulaUniversity of Denver 2:15pm Tuesday 20th April 2010 Room 215, Richard Berry Building 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. |
Thrackles and related graph drawingsGrant CairnsSchool of Engineering and Mathematical Sciences La Trobe University 2:15pm Tuesday 13th April 2010 Room 215, Richard Berry Building 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. |
Load balancing and random graphsNick WormaldDepartment of Combinatorics and Optimization Waterloo University 2:15pm Tuesday 30th March 2010 Room 215, Richard Berry Building 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. |
Hadwiger's Graph Colouring ConjectureDavid R. WoodDepartment of Mathematics and Statistics University of Melbourne 2:15pm Tuesday 16th March 2010 Room 215, Richard Berry Building 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. |
The Degree-Diameter Problem:
Guillermo Pineda-Villavicencio
|
Cores of vertex-transitive graphsPh.D. Confirmation talkRicky Rotheram The University of Melbourne 1:15pm Tuesday 2nd March 2010 Room 215, Richard Berry Building 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. |
Characterizations and algorithms
Rebecca Robinson
|
A combinatorial approach to Tutte polynomial inequalitiesArun P. ManiMonash University 2:15 - 3:15pm, Tuesday 8th September 2009 Room 107, Richard Berry Building 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. |
Rook polynomials, matchings and permanentsIan WanlessSchool of Mathematical Sciences Monash University 2:15 - 3:15pm, Tuesday 1st September 2009 Room 107, Richard Berry Building 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
|
Optimization Problems: Duality and Computational ModelsPrabhu ManyemUniversity of Ballarat & Shanghai University 2:15 - 3:15pm, Tuesday 11th August 2009 Room 107, Richard Berry Building 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). |
How to use the Lovász Local LemmaDavid WoodDepartment of Mathematics & Statistics The University of Melbourne 2:15 - 3:15pm, Tuesday 4th August 2009 Room 107, Richard Berry Building 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. |
Imprimitive symmetric graphs with cyclic blocksSanming ZhouDepartment of Mathematics and Statistics The University of Melbourne 2:15 - 3:15pm, Tuesday 21st July 2009 Room 107, Richard Berry Building 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. |
Two domination parameters in graphsGuangjun XuDepartment of Mathematics & Statistics The University of Melbourne 2:15 - 3:15pm, Tuesday 30th June 2009 Room 107 (might be changed to 213), Richard Berry Building 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. |
Symmetric graphs and domination in graphsGuangjun XuDepartment of Mathematics & Statistics The University of Melbourne 2:15 - 3:15pm, Tuesday 23rd June 2009 Room 213, Richard Berry Building A finite graph $\Gamma$ is said to be $G$-symmetric if $\Gamma$ admits $G$ as a group of automorphisms such that $G$ acts transitively on the ordered pairs of adjacent vertices of $\Gamma$. In most cases, $G$ acts imprimitively on the vertices of $\Gamma$, and we call such graphs imprimitive $G$-symmetric graphs. In this talk, I will introduce the geometric approach proposed by Gardiner and Praeger in 1995 for studying imprimitive symmetric graphs. According to this approach, three configurations can be associated with $(\Gamma, {\cal B})$, where ${\cal B}$ a nontrivial $G$-invariant partition of the vertex set of $\Gamma$. I will survey some known results on imprimitive symmetric graphs obtained by using Gardiner and Praeger's approach. And present our results to one open question proposed recently. |
An Efficient Algorithm for Partial Order ProductionGwenaël JoretDépartement d'Informatique Université Libre de Bruxelles 2:15 - 3:15pm, Tuesday 16th June 2009 Room 213, Richard Berry Building 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. |
Why Study the Crossing Number of a Graph?David WoodDepartment of Mathematics & Statistics The University of Melbourne 2:15 - 3:15pm, Tuesday 9th June 2009 Room 213, Richard Berry Building 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). |