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.     

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).     

The irredundant ramsey number s(3,3,3) = 13

Let G₁, G₂,. …, G_t be an arbitrary t-edge coloring of K_n, where for each i ∈ {1,2, …, t}, G_i is the spanning subgraph of K_n consisting of all edges colored with the ith color. The irredundant Ramsey number s(q₁, q₂, …, q_t) is defined as the smallest integer n such that for any t-edge coloring of K_n, _i has an irredundant set of size q_i for at least one i ∈ {1,2, …,t}. It is proved that s(3,3,3) = 13, a result that improves the known bounds 12 ≤ s(3,3,3) ≤ 14.     

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.     

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.     

The Ramsey number R(3, t) has order of magnitude t2/log t

The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of order s or a blue complete graph of order t. This paper proves that R(3, t) is bounded below by (1 – o(1))t/²/log t times a positive constant. Together with the known upper bound of (1 + o(1))t²/log t, it follows that R(3, t) has asymptotic order of magnitude t²/log t. © 1995 John Wiley & Sons, Inc.     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

CO‐irredundant Ramsey numbers for graphs

The study of the CO‐irredundant Ramsey numbers t(n₁, ···, n_k) is initiated. It is shown that several values and bounds for these numbers may be obtained from the well‐studied generalized graph Ramsey numbers and the values of t(4, 5), t(4, 6) and t(3, 3, m) are calculated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 258–268, 2000     

An upper bound for the Folkman number F(3, 3; 5)

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.     

(2, 3, k)-generated groups of large rank

For any fixed k 3 7k \geq 7 there exist integers n_k and a_k such that if the ring R is generated by a set of m elements t₁,...,t_m, where 2t₁-t₁²2t_1-t_1^2 is a unit of finite multiplicative order, and n 3 n_k+ma_kn \geq n_k+ma_k, then the group E_n(R) generated by elementary transvections is an epimorphic image of the triangle group D(2,3,k).\Delta (2,3,k).     

Large dense neighbourhoods and turán's theorem

Let t_r(n) denote the number of edges in the complete r-partite graph on n vertices whose colour classes are as equal in size as possible. It is proved that if G is a simple graph on n vertices and more than t_r(n) edges, and if v is any vertex of maximum degree m in G, then the subgraph of G induced by the neighbours of v has more than t_r?1(m) edges. Examples are given to demonstrate the sharpness of this theorem, and its algorithmic implications are noted.     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Star-factors of tournaments

Let S_m denote the m-vertex simple digraph formed by m − 1 edges with a common tail. Let f(m) denote the minimum n such that every n-vertex tournament has a spanning subgraph consisting of n/m disjoint copies of S_m. We prove that m lg m − m lg lg m ≤ f(m) ≤ 4m² − 6m for sufficiently large m. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 141–145, 1998     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

On maximal (k,t)-sets

Summary This investigation was originally motivated by the problem of determining the maximum number of points in finiten-dimensional projective spacePG(n, s) based on the Galois fieldGF(s) of orders=p ^h (wherep andh are positive integers andp is the prime characteristic of the field), such that not of these chosen points are linearly dependent. A set ofk distinct points inPG(n, s), not linearly dependent, is called a (k, t)-set fork ₁ >k. The maximum value ofk is denoted bym _t (n+1, s). The purpose of this paper is to find new upper bounds for some values ofn, s andt. These bounds are of importance in the experimental design and information theory problems.     

Total domination in graphs with minimum degree three

A set S of vertices of a graph G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γ_t(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000     

Paired-Domination in Claw-Free Graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in claw-free graphs. Specifically, we show that γ _pr (G) ≤ (3n ? 1)/5 if G is a connected claw-free graph of order n with minimum degree at least three and that this bound is sharp.     

Irredundant ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the least value of p such that for any p-vertex graph G, either G has an irredundant set of at least n vertices or its complement G has an irredundant set of at least m vertices. The existence of these numbers is guaranteed by Ramsey's theorem. We prove that s(3, 3) = 6, s(3, 4) = 8, and s(3,5) = 12.     

The dimension of the determinantal scheme vs (t,t,2) of the catalecticant matrix

Let T be a Gorenstein sequence of a graded artinian Gorenstein ring k[x ₀,x ₁,x ₂]/I We develop a dimension formula for PGor(T) in terms of the alignment character. Based on our formula, we find a very large component of V_s (t,t,2) when s=r_t-1+1 and t is large enough. This answers Diesel’s conjecture negatively. Further we show that V_s (t,t,2) is irreducible of dimension 3s-1 for s ≤t+1,t ≥ 2 and dim V_s (t,t,2)= 3s-1 for small s. Finally an algorithm to calculate dim V_s (t,t,2) is constructed, and we find the values of dim V_s (t,t,2) for t ≤ 16.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005