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 G-A 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 self-organizing 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 red-blue graph G is a set of vertices V(G) together with two edges sets: Er(G), the red edges; and Eb(G), the blue edges. Given red-blue graphs G and H, a homomorphism of G to H is a function f : V(G) ® V(H) such that uv Î Ei(G) implies f(u)f(v) Î Ei(H), for i Î {r,b}. We write G ®H.
Given a red-blue graph G and a vertex v Î V(G), the graph Gv 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 red-blue graph.) A red-blue graph H is switch invariant if for any red-blue graph G we have G ® H if and only if Gv ® H for all v Î V(G). Switch invariant graphs arise in modeling certain constraint satisfaction problems.
We present a characterization of switch invariant red-blue graphs, plus generalize the problem to edge-coloured 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 Ï S2-d(u,S). The influence number of a graph is the maximum such value over all possible vertex subsets: h(G) = maxS Í Vh(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: hT(G) = maxS Í 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 all-carbon molecule Cn, is cubic, with only pentagonal and hexagonal faces (12 and n/2-10, 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 closo-series of borane anions, BN HN2-. 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,...,2n-1} 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 d-dimensional n×n×¼×n silver cube? We propose that a "diagonal" should be a "maximum independent set in the d-th 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(n-1)+1 so that, for each cell c on the "diagonal", every symbol appears once in one of the d(n-1)+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. Verdian-Rizi.
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 self-dual embeddings of strongly regular self-complementary 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 self-dual 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 Lee-distance error correcting codes) that a perfect dominating set of distance d in the n-dimensional torus Ck ×¼×Ck 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 t-dependence and t-improper chromatic numbers of the Erdös-Rényi random graph. As usual, Gn,p denotes a random graph with vertex set [n] = {1,...,n} in which the edges are chosen independently at random with probability p. The t-dependence number at(G) of a graph G is the maximum size of a t-dependent set-a vertex subset which induces a subgraph of maximum degree at most t. The t-improper chromatic number ct(G) is the smallest number of colours needed in a t-improper colouring-a colouring of the vertices in which colour classes are t-dependent sets. Note that ct(G) ³ |V(G)|/at(G) and ct(G) ³ ct+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(Gn,p) was once one of the central open problems in random graph theory. We consider a fixed edge-probability p where 0 < p < 1, and t=t(n). Our results on ct(Gn,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ös-Gallai 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 3-hypergraphs are still unknown.
A simple 3-hypergraph 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) = (d1,d2,...,dn), such that d1 ³ d2 ³ ¼ ³ dn. We ask when a given sequence D is the degree sequence of a simple 3-hypergraph?
It is still unknown whether this problem has a polynomial-time algorithmic solution, or whether it is NP-complete. Recently Kocay and Li showed that any two 3-hypergraphs with the same degree sequence can be transformed into each other by a sequence of operations known as trades. The proof is based on null-hypergraphs. We describe the structure of null-hypergraphs, and a closely related NP-complete problem for 3-hypergraph 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 polynomial-time recognition algorithms for probe cographs, probe P4-reducible graphs, probe P4-sparse graphs, and probe splitgraphs.
Joint work with Maw-Shang Chang, Ton Kloks, Dieter Kratsch and Sheng-Lung 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 1-factor (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 near-decomposition. 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 ¹ pa, where p is prime and a > 1, and that these constraints are necessary. We prove that when n is even, cyclic Hamiltonian near-decompositions of the complete graph on n vertices exist if and only if n ¹ 2pa 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 non-adjacent. 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 120-cell.
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 u-w path containing v or some shortest v-w 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 NP-hard.
Joint work with J. Peters-Fransen.
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 block-intersection graph GD is the graph having vertex set B such that two vertices b1 and b2 are adjacent if and only if b1 and b2 have non-empty intersection.
Hare showed in 1995 that if D is a PBD(v,K,1) with minK \geqslant 3, then GD is edge-pancyclic (i.e., each edge of GD is contained in a cycle of each length l = 3,4,...,|V(GD)|). In this presentation we consider block-intersection 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 so-called 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 Roy-Warshall'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 k-uniform hypergraph H with n vertices which does not contain a given linear k-uniform 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 NP-complete.
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 Vc. 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 Î Vc and v Î Vc¢, 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 Î Vc and v Î Vc¢, u £ v. This problem is the well-known 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 Î Vc and v Î Vc¢ in a component induced by VcÈVc¢, u £ v.
This is a joint work with Arvind Gupta, Jan van den Heuvel, Jan Manuch, and Xiaohong Zhao.
A graph is circular-perfect if each of its induced subgraphs has the same circular chromatic number as its circular clique number. A graph is called minimally circular-imperfect if the graph itself is not circular-perfect but each of its proper induced subgraphs is. One approach to study the circular-perfect graphs is to characterize the minimally circular-imperfect graphs. In this talk, some results on minimally circular-imperfect graphs are presented.