All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

ASYMPTOTIC BOUNDS FOR IRREDUNDANT RAMSEY NUMBERS

Abstract

The irredundant Ramsey number s(m,n) is the smallest N such that in every red-blue colouring of the edges of K_N , either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We prove an asymptotic lower bound for s(m, n).     

Asymptotic bounds for irredundant and mixed Ramsey numbers

The irredundant Ramsey number s(m, n) is the smallest N such that in every red-blue coloring of the edges of K_N, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n-element irredundant set is replaced by an n-element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t(3, n). © 1993 John Wiley & Sons, Inc.     

On irredundant Ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the smallest p such that in every two-coloring of the edges of K_p using colors red (R) and blue (B), either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the form s(3, n) and prove that 18 ≤ s(3,7) ≤ 19.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

On a problem of Erdős and Rado

We give some improved estimates for the digraph Ramsey numbersr(K _n ^* ,L _m ), the smallest numberp such that any digraph of orderp either has an independent set ofn vertices or contains a transitive tournament of orderm. By results of Baumgartner and of Erdős and Rado, this is equivalent to the following infinite partition problem: for an infinite cardinal κ and positive integersn andm, find the smallest numberp such that

A note on constructive methods for ramsey numbers

Let r(k) denote the least integer n-such that for any graph G on n vertices either G or its complement G contains a complete graph K_k on k vertices. in this paper, we prove the following lower bound for the Ramsey number r(k) by explicit construction: r(k) ≥ exp (c(Log k)^4/3[(log log k)^1/3] for some constant c> 0.     

On the Ramsey number of trees versus graphs with large clique number

Chvátal established that r(T_m, K_n) = (m – 1)(n – 1) + 1, where T_m is an arbitrary tree of order m and K_n is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K_n could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that K_n can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(T_m, K_n –tK₂) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where T_m is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].     

Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Ramsey unsaturated and saturated graphs

A graph is Ramsey unsaturated if there exists a proper supergraph of the same order with the same Ramsey number, and Ramsey saturated otherwise. We present some conjectures and results concerning both Ramsey saturated and unsaturated graphs. In particular, we show that cycles C_n and paths P_n on n vertices are Ramsey unsaturated for all n ≥ 5. © 2005 Wiley Periodicals, Inc.     

The mixed irredundant Ramsey numbers t(3, 7) = 18 and t(3, 8) = 22

Abstract

The mixed irredundant Ramsey number t(m, n) is the smallest natural number t such that if the edges of the complete graph K_t on t vertices are arbitrarily bi-coloured using the colours blue and red, then necessarily either the subgraph induced by the blue edges has an irredundant set of cardinality m or the subgraph induced by the red edges has an independent set of cardinality n (or both). Previously it was known that 18 ≤ t(3, 7) ≤ 22 and 18 ≤ t(3, 8) ≤ 28. In this paper we prove that t(3, 7) = 18 and t(3, 8) = 22.     

The Ramsey number for a cycle of length six versus a clique of order eight

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_m denote a cycle of length m and K_n a complete graph of order n. In this paper, it is shown that R(C₆,K₈)=36.     

Lower bounds for lower Ramsey numbers

For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).     

A class of self-complementary graphs and lower bounds of some ramsey numbers

A method is described of constructing a class of self-complementary graphs, that includes a self-complementary graph, containing no K₅, with 41 vertices and a self-complementary graph, containing no K₇, with 113 vertices. The latter construction gives the improved Ramsey number lower bound r(7, 7) ≥ 114.     

The irredundant ramsey number s(3, 7)

The irredundant Ramsey number s(m, n) is the smallest p such that for every graph G with p vertices, either G contains an n-element irredundant set or its complement G contains an m-element irredundant set. Cockayne, Hattingh, and Mynhardt have given a computer-assisted proof that s(3, 7) = 18. The purpose of this paper is to give a self-contained proof of this result. © 1995 John Wiley & Sons, Inc.     

GENERALISED MAXIMAL INDEPENDENCE AND CLIQUE NUMBERS OF GRAPHS

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let β_k, (G) (w_k(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously β_k(G) = w_k([Gbar]). For the sequence m₁ ? m₂ ?…? m_n = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that w_k(G) = m_k for k = 1,2,…,n and w(G) = r (equivalently, β_k(G) = m_k for k = 1,2,…,n and β(G) = r). Define s_k(?,m) to be the largest integer such that for every graph G with at most s_k(?,m) vertices, β_k(G) ? ? or w_k(G) ? m. Exact values for s_k(?,m) if k ≥ 2 and upper and lower bounds for s₁(?,m) are de termined.     

Untangling Polygons and Graphs

Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C _n while keeping Ω(n ^2/3) vertices fixed. For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)^2/3) vertices are fixed in every untangling of δ.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Cycle systems without 2-colorings

In an m-cycle system C of order n the blocks are the vertex sets of n(n−1)/(2m) cycles C_i such that each edge of the complete graph K_n belongs to precisely one cycle C_i E C. We prove the existence of m-cycle systems that admit no vertex partition into two classes in such a way that each class meets every cycle of C. The proofs apply both constructive and probabilistic methods, and also some old and new facts about Steiner Triple Systems without large independent sets. © 1996 John Wiley & Sons, Inc.