Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Uma caracterização de grafos imersíveis

Este trabalho é motivado pelo resultado de Berge, que é uma generalização do teorema de Tutte o qual expressamos na forma: Dado o grafo G de ordem |V(G)| eni(G) o número de arestas em um emparelhamento máximo, existe um conjunto X de vértices de G tal que |V(G)|+|X| - ômega(G\X) - 2n(G)=0, onde ômega(G\X) é o número de componentes de ordem ímpar de G\X. Tal expressão chamamos a equação de Tutte-Berge associada de G, e escrevemos simplesmente T(G; X)=0. Os grafos podem ser classificados a partir das soluções da equação de Tutte-Berge. Um grafo G é chamado imersível se, e somente se, T(G; X)=0 possui pelo menos um conjunto solução não vazio de vértices, e G é denominado não imersível se, e somente se, o conjunto vazio é a única solução de T(G; X)=0. O resultado principal deste artigo é a caracterização de grafos imersíveis pelos conjuntos antifatores completos, além disso, provamos que os grafos fatoráveis estão contidos na classe dos imersíveis.

Inferência estatística clássica para a confiabilidade de rede de coautoria com enfoque nos vértices

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Let k and l be positive integers. With a graph G, we associate the quantity c(k,l)(G), the number of k-colourings of the edge set of G with no monochromatic matching of size l. Consider the function c(k,l) : N --&gt; N given by c(k,l)(n) = max {c(k,l)(G): vertical bar V(G)vertical bar = n}, the maximum of c(k,l)(G) over all graphs G on n vertices. In this paper, we determine c(k,l)(n) and the corresponding extremal graphs for all large n and all fixed values of k and l.

Weak quasi-randomness for uniform hypergraphs

We study quasi-random properties of k-uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung-Graham-Wilson theorem for quasi-random graphs. Moreover, let K(k) be the complete graph on k vertices and M(k) the line graph of the graph of the k-dimensional hypercube. We will show that the pair of graphs (K(k),M(k)) has the property that if the number of copies of both K(k) and M(k) in another graph G are as expected in the random graph of density d, then G is quasi-random (in the sense of the Chung-Graham-Wilson theorem) with density close to d. (C) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 1-38, 2012

Common multiples of complete graphs and a 4-cycle

A graph G is a common multiple of two graphs H-1 and H-2 if there exists a decomposition of G into edge-disjoint copies of H-1 and also a decomposition of G into edge-disjoint copies of H-2. In this paper, we consider the case where H-1 is the 4-cycle C-4 and H-2 is the complete graph with n vertices K-n. We determine, for all positive integers n, the set of integers q for which there exists a common multiple of C-4 and K-n having precisely q edges. (C) 2003 Elsevier B.V. All rights reserved.

Some equitably 3-colourable cycle decompositions

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),..., c(k). If an m-cycle C in G has n(i) vertices coloured c(i), i = 1, 2,..., k, and (i) - n(j) less than or equal to 1 for any i, j is an element of {1, 2,..., k}, then C is equitably k-coloured. An m-cycle decomposition C of a graph G is equitably k-colourable if the vertices of G can be coloured so that every m-cycle in C is equitably k-coloured. For m = 4,5 and 6, we completely settle the existence problem for equitably 3-colourable m-cycle decompositions of complete graphs and complete graphs with the edges of a 1-factor removed. (C) 2004 Elsevier B.V. All rights reserved.

Steiner trade spectra of complete partite graphs

The Steiner trade spectrum of a simple graph G is the set of all integers t for which there is a simple graph H whose edges can be partitioned into t copies of G in two entirely different ways. The Steiner trade spectra of complete partite graphs were determined in all but a few cases in a recent paper by Billington and Hoffman (Discrete Math. 250 (2002) 23). In this paper we resolve the remaining cases. (C) 2004 Elsevier B.V. All rights reserved.

Some equitably 3-colourable cycle decompositions of complete equipartite graphs

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),.. , c(k). If an m-cycle C in G has n(i) vertices coloured c(i), i = 1, 2,..., k, and vertical bar n(i) - n(j)vertical bar <= 1 for any i, j is an element of {1, 2,..., k}, then C is said to be equitably k-coloured. An m-cycle decomposition C of a graph G is equitably k-colourable if the vertices of G can be coloured so that every m-cycle in W is equitably k-coloured. For m = 3, 4 and 5 we completely settle the existence question for equitably 3-colourable m-cycle decompositions of complete equipartite graphs. (c) 2005 Elsevier B.V. All rights reserved.

On a Class of Vertex Folkman Numbers

Let a1 , . . . , ar, be positive integers, i=1 ... r, m = ∑(ai − 1) + 1 and p = max{a1 , . . . , ar }. For a graph G the symbol G → (a1 , . . . , ar ) means that in every r-coloring of the vertices of G there exists a monochromatic ai -clique of color i for some i ∈ {1, . . . , r}. In this paper we consider the vertex Folkman numbers F (a1 , . . . , ar ; m − 1) = min |V (G)| : G → (a1 , . . . , ar ) and Km−1 ⊂ G} We prove that F (a1 , . . . , ar ; m − 1) = m + 6, if p = 3 and m ≧ 6 (Theorem 3) and F (a1 , . . . , ar ; m − 1) = m + 7, if p = 4 and m ≧ 6 (Theorem 4).

Sequences of Maximal Degree Vertices in Graphs

2000 Mathematics Subject Classification: 05C35.

A New Method for Computing the Eccentric Connectivity Index of Fullerenes

ACM Computing Classification System (1998): G.2.2, G.2.3.