We consider classes of graphs which are easily seen to have many perfect matchings. The class of grid graphs is our main example. We then consider what properties to impose on choosing a subset of vertices A Í V(G) for vertex deletion in a graph G (from such a class) so that the vertex deleted subgraph GA has a perfect matching. Certain conditions are easy. An even number of vertices must be deleted. If the graph is bipartite then the deleted vertices must have equal numbers from both parts of the bipartition. Also one cannot delete all the neighbours of a given vertex.
We obtain two results. In one, the deleted vertices are confined to the periphery of the graph and in the other the deleted vertices are required to be far apart. The motivation was a result of Jamison and Lockner presented at CGTC 34 (2003) but we can see this as an alternative to the edge extendibility investigations of Plummer et al.
Much recent attention has focussed on the rigorous design and analysis of models for the web graph and other massive selforganizing networks. Models for these networks often incorporate copying in their design, where a new node imperfectly duplicates some of the link structure of an existing node. The motivation for copying models comes from the fact that each node acts as an independent agent, which will base its decision on how to link to the existing network on local knowledge. As a result, the neighbourhood of a new node will often be similar to that of an existing node. Consideration of copying models and their limiting behaviour have led to the discovery of new connections between random graphs, graph homomorphisms, vertex pursuit games, and infinite graphs.
This is joint work with Manuel Bodirsky, Peter Cameron, Dejan Deli\'c, Jeannette Janssen, and Changping Wang.
A redblue graph G is a set of vertices V(G) together with two edges sets: E_{r}(G), the red edges; and E_{b}(G), the blue edges. Given redblue graphs G and H, a homomorphism of G to H is a function f : V(G) ® V(H) such that uv Î E_{i}(G) implies f(u)f(v) Î E_{i}(H), for i Î {r,b}. We write G ®H.
Given a redblue graph G and a vertex v Î V(G), the graph G^{v} is obtained from G by switching the colour of edge incident with v. (This process is analogous to Seidel switching when G is a complete redblue graph.) A redblue graph H is switch invariant if for any redblue graph G we have G ® H if and only if G^{v} ® H for all v Î V(G). Switch invariant graphs arise in modeling certain constraint satisfaction problems.
We present a characterization of switch invariant redblue graphs, plus generalize the problem to edgecoloured graphs with m edge colours.
This is joint work with Timothy Graves.
Recently, the study of social networks has given rise to a graph parameter known as the influence number: h(G). This parameter measures the influence that a vertex subset S has on the remaining vertices such that each vertex not in S is influenced by the closest member of S as follows: h(S) = å_{u Ï S}2^{d(u,S)}. The influence number of a graph is the maximum such value over all possible vertex subsets: h(G) = max_{S Í V}h(S). A natural extension to the influence number allows each vertex not in S to be influenced by every vertex in S. This gives the total influence number: h_{T}(G) = max_{S Í V}[å_{u Î S} å_{v Ï S} 2^{d(u,v)}]. Other applications include facility location problems where the quality of service decays exponentially with respect to distance. This talk will explore some of the basic results involving the influence and total influence numbers of a graph.
Graph searching and graph sweeping are often used as real world models in which mobile agents move to capture a mobile intruder. In graph searching, the intruder can only be located on vertices, while in graph sweeping, the intruder can also be located on edges. The most common problem examined with these models is to find the fewest agents which can guarantee the intruder's capture. However, in some situations, agents are "cheap", and we may then insist the intruder be captured quickly. We examine several such cases in variations of the the graph searching and sweeping models.
The study of the concepts of domination, independence and irredundance has led to many generalisations of these concepts in the literature. We consider a method for categorising many of these generalisations into a general framework. The framework is used to find connections between the generalised concepts and allows for many theorems (regarding these connections) to be proven at once.
An independent dominating set D is any set of vertices in a graph G such that no vertices in D are adjacent, but every vertex in V(G)  D is adjacent to a vertex in D. The independent domination number of G, denoted i(G), is the cardinality of a minimum independent dominating set.
The following upper bounds have been found by Bollobás & Cockayne
and MacGillivray & Seyffarth, respectively:
 

A fullerene polyhedron, representing an allcarbon molecule C_{n}, is cubic, with only pentagonal and hexagonal faces (12 and n/210, respectively, by Euler's theorem). The spectrum of the adjacency matrix contains a great deal of qualitative chemical information on optimum electron count, electronic configuration, stability and reactivity of the molecule. Connections between graph theory and these chemical models will be discussed. Cospectral fullerene graphs would be of interest as representing molecules with structures that were different but with (some) identical properties. As yet, no cospectral fullerenes are known, but many pairs of fullerenes with cospectral duals have now been found (P. W. Fowler and M. Duncan, to be published). The dual of a fullerene graph is also a polyhedral graph, having all faces triangular, 12 vertices of degree 5 and all others of degree 6; considered as the skeleton of a molecule, it is a model for large boron hydrides, based on extrapolation of the known clososeries of borane anions, B_{N} H_{N}^{2}. A construction for (infinite) families of cospectral fullerene duals will be presented.
An n ×n matrix is silver if, for i=1,...,n, every symbol in {1,2,...,2n1} appears as an entry in either row i or column i.
An IMO 1997 question introduced this definition, and asked whether a silver matrix of order 1997 exists. (In fact, one exists if and only if n=1 or n is even.) In this paper we investigate higher dimensional analogs, silver cubes.
Finding the correct generalization is the first challenge. The cells on the main diagonal of a silver matrix are treated specially. What should serve as a "diagonal" in a ddimensional n×n×¼×n silver cube? We propose that a "diagonal" should be a "maximum independent set in the dth cartesian power of the complete graph of order n." This definition is motivated by "minimal defining sets" for colouring such graphs. The challenge is to label the cells with symbols 1,2,...,d(n1)+1 so that, for each cell c on the "diagonal", every symbol appears once in one of the d(n1)+1 cells orthogonally translated from c. We present constructions, nonexistence proofs and connections with coding theory and projective geometry.
This is joint work with M. Ghebleh, E. Mahmoodian and M. VerdianRizi.
We introduced the injective chromatic number in [1] but it had been studied in different guises before. In this talk we review previous results and give new bounds on the number for some classes of graphs.
This is joint work with Alain Doyon, André Raspaud and Weifan Wang.
A dominating set S of a graph is a set of vertices such that every vertex of the graph is either in S or adjacent to some vertex of S. In particular, the dominating set is considered static and all vertices of the graph are dominated all of the time. In many applications this may not be practical as resources are simply too limited. Hence we might allow vertices to not be dominated for certain periods of time as long as such time intervals are not excessive. Thus we could allow each member of our set to either remain fixed or move to an adjacent vertex in one unit of time. What can be said about the time vertices are not monitored if the dominating set is cut to some fraction of the original number required or by a fixed number? Although more questions than answers will be given, some observations will be outlined.
An infinite family of selfdual embeddings of strongly regular selfcomplementary graphs is presented. These embeddings are very highly structured and have the property that if one draws the dual on the same surface, without moving any vertices, the resulting embedding of the complement is also selfdual and all four embeddings are map isomorphic.
A perfect dominating set S of distance d in a graph G is a set of its vertices so that each vertex of G is at distance at most d from exactly one vertex of S. In 1968 Golomb and Welsh conjectured (they formulated their conjecture in terms of Leedistance error correcting codes) that a perfect dominating set of distance d in the ndimensional torus C_{k} ×¼×C_{k} exists only in the case for n=1 and any d or n=2 and any d or d=1 and any n. Despite a lot of effort by researchers both in graph theory and in coding theory the conjecture is still open although there are plenty of partial results supporting the conjecture. In this talk we will discuss some variations of the conjecture that are motivated by an application in computer science.
We consider the tdependence and timproper chromatic numbers of the ErdösRényi random graph. As usual, G_{n,p} denotes a random graph with vertex set [n] = {1,...,n} in which the edges are chosen independently at random with probability p. The tdependence number a^{t}(G) of a graph G is the maximum size of a tdependent seta vertex subset which induces a subgraph of maximum degree at most t. The timproper chromatic number c^{t}(G) is the smallest number of colours needed in a timproper colouringa colouring of the vertices in which colour classes are tdependent sets. Note that c^{t}(G) ³ V(G)/a^{t}(G) and c^{t}(G) ³ c^{t+1}(G) for any graph G.
Clearly, when t = 0, we are considering the independence number and chromatic number of random graphs, and the problem of determining the asymptotic behaviour of the chromatic number c(G_{n,p}) was once one of the central open problems in random graph theory. We consider a fixed edgeprobability p where 0 < p < 1, and t=t(n). Our results on c^{t}(G_{n,p}) break into three ranges for t(n). We say that a property holds asymptotically almost surely (a.a.s.) if it holds with probability ® 1 as n ® ¥.
This is joint work with Colin McDiarmid.
The ErdösGallai conditions are necessary and sufficient conditions for the existence of a simple graph with a given degree sequence. Much work has been done characterizing the polytope of degree sequences of simple graphs. The corresponding conditions for 3hypergraphs are still unknown.
A simple 3hypergraph G consists of a set V of vertices and E of edges, such that each edge is a triple u,v,w of distinct vertices. Repeated triples are not allowed in G. The degree of a vertex v is deg(v), the number of triples containing v. The degree sequence of G is the sequence of degrees D(G) = (d_{1},d_{2},...,d_{n}), such that d_{1} ³ d_{2} ³ ¼ ³ d_{n}. We ask when a given sequence D is the degree sequence of a simple 3hypergraph?
It is still unknown whether this problem has a polynomialtime algorithmic solution, or whether it is NPcomplete. Recently Kocay and Li showed that any two 3hypergraphs with the same degree sequence can be transformed into each other by a sequence of operations known as trades. The proof is based on nullhypergraphs. We describe the structure of nullhypergraphs, and a closely related NPcomplete problem for 3hypergraph degree sequences.
In this paper we consider the recognition of some probe graph classes. Given a class of graphs G, a graph G is a probe graph of G if its vertices can be partitioned into a set P of probes and an independent set N of nonprobes, such that G can be extended to a graph of G by adding edges between certain nonprobes. We show that there are polynomialtime recognition algorithms for probe cographs, probe P_{4}reducible graphs, probe P_{4}sparse graphs, and probe splitgraphs.
Joint work with MawShang Chang, Ton Kloks, Dieter Kratsch and ShengLung Peng.
It has been proven that the complete graph on n vertices can be decomposed into Hamiltonian cycles, whenever n is odd. Similarly, if we remove a 1factor (perfect matching) from the complete graph on an even number of vertices, the remaining graph can always be decomposed into Hamiltonian cycles; this is what is referred to as a neardecomposition. To make the problem interesting again, we put constraints on the Hamiltonian cycles that we allow to be in the decomposition. A cyclic Hamiltonian decomposition of the complete graph is a decomposition of the complete graph into Hamiltonian cycles, in such a way as to ensure that rotating any cycle in the decomposition gives us a (possibly different) cycle in the decomposition. It has been proven that a cyclic Hamiltonian decomposition of the complete graph on n vertices always exists when n is odd, as long as n ¹ 15 and n ¹ p^{a}, where p is prime and a > 1, and that these constraints are necessary. We prove that when n is even, cyclic Hamiltonian neardecompositions of the complete graph on n vertices exist if and only if n ¹ 2p^{a} where p is prime, and n is either 2 or 4 (mod 8).
An independent set of a graph G is a set of vertices of G which are pairwise nonadjacent. There are many applications for which the input is a graph G with a large symmetry group and the goal is to generate either all of the independent sets or all of the maximum independent sets up to isomorphism. We present a very fast practical algorithm for this problem. The tactic can also be applied to many other problems: some examples are generation of all colourings or matchings of a graph up to isomorphism. Two applications are given to illustrate the utility of this algorithm: finding all independent sets of the C60 and C70 fullerenes, and also the problem of finding a maximum set of vertices at distance four or more in the 120cell.
This is joint work with Patrick Fowler.
Let G be a connected graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest uw path containing v or some shortest vw path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. A smallest strong resolving set for G is called a strong basis for G and its cardinality the strong dimension of G. We begin with a motivation and an overview of this invariant and a related invariant, namely the metric dimension of a graph. We then show that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, this invariant is shown to be NPhard.
Joint work with J. PetersFransen.
A pairwise balanced design PBD(v,K,l) consists of a set V of cardinality v, a set K of positive integers, and a set B of subsets of V with the properties that b Î K for each b Î B, and each pair of elements from V occurs in exactly l of the subsets in B. The elements of B are known as the blocks of the design.
Given a combinatorial design D with block set B, its blockintersection graph G_{D} is the graph having vertex set B such that two vertices b_{1} and b_{2} are adjacent if and only if b_{1} and b_{2} have nonempty intersection.
Hare showed in 1995 that if D is a PBD(v,K,1) with minK \geqslant 3, then G_{D} is edgepancyclic (i.e., each edge of G_{D} is contained in a cycle of each length l = 3,4,...,V(G_{D})). In this presentation we consider blockintersection graphs of pairwise balanced designs PBD(v,K,l) for which l\geqslant 2.
This is joint work with Graham Case.
A bipolar weighted digraph is a digraph together with a weight function and a sign function on the arcs such that the weight of each arc lies in the interval [0,1] and no two parallel arcs have the same sign. Bipolar weighted digraphs are natural models for socalled fuzzy cognitive maps, which are used in science, engineering, and the social sciences to represent a body of knowledge. It has been noted in the literature that a transitive closure of a bipolar weighted digraph contains useful new information for the fuzzy cognitive map it models.
It is natural to define a transitive closure of a bipolar weighted digraph D=(V,A) as a bipolar weighted digraph D^{*}=(V,A^{*}) such that an arc (u,v) of sign s is in A^{*} if and only if D has a directed (u,v)walk of sign s (where the sign of a directed walk is defined as the product of signs of all its arcs). But what weight should be assigned to (u,v) in D^{*}? We propose two models: the bipolar fuzzy digraph model, which has been previously considered in some form in fuzzy systems research, and the new bipolar random digraph model. A bipolar fuzzy digraph consists of two fuzzy relations on the set V (that is, the arc weights are viewed as degrees of membership), and its transitive closure is a combined transitive closure of the two fuzzy relations. In a random digraph model, on the other hand, the arc weights are viewed as probabilities, and the weight of an arc (u,v) of sign s in the transitive closure is defined as the probability of having a directed (u,v)walk of sign s in D. While a version of RoyWarshall's algorithm efficiently computes the transitive closure of a bipolar fuzzy digraph, the problem is computationally hard for bipolar random digraphs. However, we describe several approaches that allow computation at least for the types and sizes of fuzzy cognitive maps we have dealt with in practice.
A hypergraph is linear if every two hyperedges share one point at most. We investigate the following question. What is the maximum possible number of edges in a linear kuniform hypergraph H with n vertices which does not contain a given linear kuniform hypergraph G as a subgraph? We show applications to geometry and number theory.
We introduce three variants of proper colorings with imposed partial ordering on the set of colors and will present dichotomy theorems that separate these problems into tractable and NPcomplete.
Vertices of all considered graphs are integers from 1 to V(G), hence they form a linearly ordered set (V (G), £ ). The set of vertices colored c will be denoted by V_{c}. Given a partially ordered set (poset) (C,\preceq) of colors, in the first problem we want to (properly) color vertices of G by colors in C (color G by poset C) such that for any two colors c and c¢ if c\preceq c¢ then for any two vertices u Î V_{c} and v Î V_{c¢}, u £ v. Thus, if \preceq is the empty relation on C, then the problem is whether G can be properly colored with C colors, a well known graph coloring problem.
In the second problem, we want to color G by poset C such that for any two colors c and c¢ if c\preceq c¢ then for any two adjacent vertices u Î V_{c} and v Î V_{c¢}, u £ v. This problem is the wellknown directed graph homomorphism problem whose dichotomy was extensively studied.
In the last problem, we want to color G by poset C such that for any two colors c and c¢ if c\preceq c¢ then for any two vertices u Î V_{c} and v Î V_{c¢} in a component induced by V_{c}ÈV_{c¢}, u £ v.
This is a joint work with Arvind Gupta, Jan van den Heuvel, Jan Manuch, and Xiaohong Zhao.
A graph is circularperfect if each of its induced subgraphs has the same circular chromatic number as its circular clique number. A graph is called minimally circularimperfect if the graph itself is not circularperfect but each of its proper induced subgraphs is. One approach to study the circularperfect graphs is to characterize the minimally circularimperfect graphs. In this talk, some results on minimally circularimperfect graphs are presented.