Anthony Bonato

The cop density of a graph (2008)

Abstract. We consider homomorphism properties of a random graph G(n, p), where p is a function of n. A core H is great if for all e ∈ E(H), there is some homomorphism from H −e to H that is not...

Anthony Bonato, Geňa Hahn, Changping Wang

Abstract. We consider the game of Cops and Robber played with infinitely many cops on countable graphs. We give a sufficient condition— the strongly 1-e.c. property—for the cop number to be...

A NOTE ON UNIQUELY H-COLOURABLE GRAPHS (2008)

MATCHINGS DEFINED BY LOCAL CONDITIONS (2008)

Abstract. For a graph H, we compare two notions of uniquely H-colourable graphs, where one is defined via automorphisms, the second by vertex partitions. We prove that the two notions of uniquely...

Anthony Bonato, Alexandru Costea

Abstract. A graph has the neighbour-closed-co-neighbour, or ncc property, if for each of its vertices x, the subgraph induced by the neighbour set of x is isomorphic to the subgraph induced by the...

information (2008)

Anthony Bonato, Jeannette Janssen, Wilfrid Laurier

Limits and power laws of models for the

THE SEARCH FOR N-E.C. GRAPHS (2008)

INFINITE LIMITS AND ADJACENCY PROPERTIES OF A GENERALIZED COPYING MODEL (2008)

Abstract. Almost all finite graphs have the n-e.c. adjacency property, although until recently few explicit examples of such graphs were known. We survey some recently discovered families of explicit...

NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS (2008)

Abstract. We present a new model for self-organizing networks such as the web graph, and analyze its limit behaviour. In the model, new vertices are introduced over time that copy the neighbourhood...

Anthony Bonato, Changping Wang

Abstract. Vertex pursuit games, such as the game of Cops and Robber, are a simplified model for network security. In these games, cops try to capture a robber loose on the vertices of the network....

Classes (2008)

On an adjacency property of almost all tournaments, accepted to Discrete Math (2008)

closed under unions and ne.c. structures

THE N-ORDERED GRAPHS- A NEW GRAPH CLASS (2008)

www.elsevier.com/locate/disc Let n be a positive integer. A tournament is called n-existentially closed (or n-e.c.) if for every subset S of n vertices and for every subset T of S, there is a vertex...

Anthony Bonato, Jeannette Janssen, Changping Wang

Abstract. For a positive integer n, we introduce the new graph class of n-ordered graphs, which generalize partial n-trees. Several characterizations are given for the finite n-ordered graphs,...

All Countable Monoids Embed into the Monoid of the Infinite Random Graph (2008)

Anthony Bonato, Dejan Delic, Igor Dolinka

We prove that the endomorphism monoid of the infinite random graph R contains as a submonoid an isomorphic copy of each countable monoid. As a corollary, the monoid of R does not satisfy any...

On an adjacency property of almost all tournaments, accepted to Discrete Math (2007)

Monatsh. Math. 135, 1±9 �2002) On Retracts of the Random Graph and Their Natural Order By (2007)

In loving memory of Claude Berge. Abstract. Let n be a positive integer. A tournament is called nexistentially closed (or n-e.c.) if for every subset S of n vertices and for every subset T of S,...

RESEARCH ARTICLE The Monoid of the Random Graph (2007)

Abstract. We prove that the natural order on the idempotents of the endomorphism monoid of the countably in®nite random graph is @0-universal; that is, it embeds every countable order. We therefore...

Anthony Bonato, Dejan Delia, Communicated Boris, M. Schein

We investigate properties of the endonorphism monoid of the countable random graph R. We show that End(R) is not regular and is not generated by its idempotents. The Rees order on the idempotents of...

Generalized pigeonhole properties of graphs and oriented graphs (2007)

Anthony Bonato, Peter J. Cameron, Dejan Delić, Stéphan Thomassé

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is...

Mathematical Logic Quarterly (2007)

Abstract. The class of width-two orders has a model companion. The model companion is complete, decidable, non-finitely axiomatizable, and has continuum many countable models. Generalizations of some...

Abstract. We prove that each ∀1 free amalgamation class K over a finite relational language L admits a countable generic structure M isometrically embedding all countable structures in K relative...

Abstract (2007)

On an adjacency property of almost all tournaments, accepted to Discrete Math (2007)

A family of universal pseudo-homogeneous G-colourable graphs

Skolem grrgys gnd Skolem lgbellings of lgdder (2007)

In loving memory of Claude Berge. Abstract. Let n be a positive integer. A tournament is called nexistentially closed (or n-e.c.) if for every subset S of n vertices and for every subset T of S,...

Catharine Baker, Patrick Kergin, Anthony Bonato

graphs

All countable monoids embed into the monoid of the infinite random graph (2007)

Anthony Bonato, Dejan Delić, Igor Dolinka

Abstract. We prove that the endomorphism monoid of the infinite random graph R contains as a submonoid an isomorphic copy of each countable monoid. As a corollary, the monoid of R does not satisfy...

Partitioning a graph into two isomorphic pieces (2007)

Anthony Bonato, Richard Nowakowski

Abstract. A simple graph G has the neighbour-closed-co-neighbour property, or ncc property, if for all vertices x of G, the subgraph induced by the set of neighbours of x is isomorphic to the...

Graphs with the 3-e.c. adjacency property constructed from affine planes (2007)

C. A. Baker, Anthony Bonato, M. N. Brown

Abstract. A graph G is 3-e.c. if for each distinct triple S of vertices, and each subset T of S, there is a vertex not in S joined to the vertices of T and to no other vertices of S. Few explicit...

On a problem of Cameron’s on inexhaustible graphs (2007)

Anthony Bonato, Dejan Deli C

Abstract. A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G: We address a question of Cameron [6], who asked which countable graphs are...

AND ST (2007)

Anthony Bonato, Peter Cameron, Dejan Deli C, Ephan Thomass

Abstract. A relational structure A satises the P(n; k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is...

ON ORIENTATIONS OF THE INFINITE RANDOM (2007)

Anthony Bonato, Dejan Deli Ć

Abstract. We answer a question of P. Cameron’s by giving examples of 2 ℵ0 many non-isomorphic acyclic orientations of the infinite random graph with a topological ordering that do not have the...

Generalized pigeonhole properties of graphs and oriented graphs (2007)

Anthony Bonato, Peter Cameron, Dejan Delić

ABSTRACT. A relational structure A satisfies the ¢ ¡ n £ k ¤ property if whenever the vertex set of A is partitioned into n nonempty parts, the substruc-ture induced by the union of some k of...

adjacency property (2007)

Anthony Bonato, W. H. Holzmann, Hadi Kharaghani

matrices and strongly regular graphs with the 3-e.c.

Limit behaviour of models for the web graph and (2007)

Anthony Bonato, Jeannette Janssen, Wilfrid Laurier

other self-organizing networks

INFINITE LIMITS OF STOCHASTIC GRAPH MODELS- DRAFT (2007)

Infinite limits of the duplication model and graph folding (2005)

Abstract. We present new generalized copying models for massive self-organizing networks such as the web graph, and analyze their limit behaviour. Our model is motivated by a desire to unify common...

A Survey of Models of the Web Graph (2004)

We study infinite limits of graphs generated by the duplication model for biological networks. We prove that with probability 1, the sole nontrivial connected component of the limits is unique up to...

Anthony Bonato, Wilfrid Laurier

The web graph has been the focus of much recent attention, with several stochastic models proposed to account for its various properties.

124 JOURNAL OF GRAPH THEORY (2004)

Infinite Limits of Copying Models of the Web Graph (2003)

DOI 10.1002/jgt.20123 Abstract: A graph has the neighbor-closed-co-neighbor, or ncc property, if for each of its vertices x, the subgraph induced by the neighbor set of x is isomorphic to the...

Bonato, Anthony, Janssen, Jeanette

Several stochastic models were proposed recently to model the dynamic evolution of the web graph. We study the infinite limits of the stochastic processes proposed to model the web graph when time...

Infinite limits of copying models of the web graph (2003)

Large families of mutually embeddable vertextransitive graphs, preprint (2003)

Abstract. Several stochastic models were proposed recently to model the dynamic evolution of the web graph. We study the infinite limits of the stochastic processes proposed to model the web graph...

Anthony Bonato, Claude Tardif

Abstract. For each infinite cardinal κ, we give examples of 2 κ many non-isomorphic vertex-transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider...

Infinite limits of copying models of the web graph (2003)

Anthony Bonato, Jeanette Janssen

Abstract. Several stochastic models were proposed recently to model the dynamic evolution of the web graph. We study the infinite limits of the stochastic processes proposed to model the web graph...

Hadamard matrices and strongly regular graphs with the 3-e.c. adjacency property, Electron (2001)

Anthony Bonato, W. H. Holzmann, Hadi Kharaghani

3-e.c. adjacency property

Tournaments and orders with the pigeonhole property (2000)

Anthony Bonato, Peter Cameron, Dejan Delić

Abstract. AbinarystructureS has the pigeonhole property (P) if every finite partition of S induces a block isomorphic to S. We classify all countable tournaments with (P); the class of orders with...

www.elsevier.com/locate/disc On an adjacency property ofalmost all graphs (2000)

Graphs with the n-e.c. adjacency property constructed from affine planes, accepted to Discrete Math

A graph is called n-existentially closed or n-e.c. ifit satis es the following adjacency property: for every n-element subset S ofthe vertices, and for every subset T of S, there is a vertex not in S...

Cathy Baker, Anthony Bonato, Julia Brown, Tam Ás

Abstract. We give new examples of graphs with the n-e.c. adjacency property. Few explicit families of n-e.c. graphs are known, despite the fact that almost all finite graphs are n-e.c. Our examples...

Generalized Pigeonhole Properties of Graphs and Oriented Graphs

Anthony Bonato, Peter Cameron, Dejan Delic, St Ephan, Stephan Thomasse

A relational structure A satis es the P(n; k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic...

Infinite Limits of Copying Models of the Web Graph