Search

Let f (d) be the smallest value for which every bridgeless graph G with diameter d admits a strong orientation G ⇀ such that the diameter of G ⇀ is at most f (d). Chvátal and Thomassen (JCT-B, 1978) established general bounds for f (d) and proved that f (2) = 6. Kwok et al. (JCT-B, 2010) showed that 9 ≤ f (3) ≤ 11. In this paper, we determine that f (3) = 9. [ABSTRACT FROM AUTHOR]

The generalized Turán number ex (n , K s , H) is the maximum number of complete graph K s in an H -free graph on n vertices. Let F k be the friendship graph consisting of k triangles. Erdős and Sós (1976) determined the value of ex (n , K 3 , F 2). Alon and Shikhelman (2016) proved that ex (n , K 3 , F k) ≤ (9 k − 15) (k + 1) n. In this paper, by using a method developed by Chung and Frankl in hypergraph theory, we determine the exact value of ex (n , K 3 , F k) and the extremal graph for any F k when n ≥ 4 k 3 . [ABSTRACT FROM AUTHOR]

For two given graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that for any graph of order N , either G contains a copy of G 1 or its complement contains a copy of G 2 . Let C m be a cycle of length m and K 1 , n a star of order n + 1 . Parsons (1975) [6] shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 for all n ≥ 2 and the equality holds if n is the square of a prime power. Let q be a prime power. In this paper, we first construct a graph Γ q on q 2 − 1 vertices without C 4 by using the Galois field F q , and then we prove that R ( C 4 , K 1 , ( q − 1 ) 2 + t ) = ( q − 1 ) 2 + q + t for q ≥ 4 is even and t = 1 , 0 , − 2 , and R ( C 4 , K 1 , q ( q − 1 ) − t ) = q 2 − t for q ≥ 5 is odd and t = 2 , 4 , . . . , 2 ⌈ q 4 ⌉ . [ABSTRACT FROM AUTHOR]

For k given graphs H 1 , ... , H k , k ≥ 2 , the k -color Ramsey number, denoted by R (H 1 , ... , H k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of H i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m , K 1 , n a star of order n + 1 and W n a wheel of order n + 1. In this paper, by using algebraic and probabilistic methods, we first give two lower bounds for (k + 1) -color Ramsey number R (C 4 , ... , C 4 , K 1 , n) for some special n , which shows the upper bound due to Zhang et al. (2019) is tight in some sense, and then establish a general lower bound for R (C 4 , ... , C 4 , K 1 , n) in terms of n and k , which extends the classical result of Burr et al. (1989). Moreover, we show that R (C 4 , ... , C 4 , K 1 , n) = R (C 4 , ... , C 4 , W n) for sufficiently large n. [ABSTRACT FROM AUTHOR]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of order and a wheel of order . Surahmat, Baskoro and Tomescu conjectured that for odd, and . In this paper, we confirm the conjecture for . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest positive integer such that for any graph of order , either contains or the complement of contains . Let denote a star of order and a wheel of order . In this paper, we show that for and . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of length and a complete graph of order . In this paper we show that for and , with the former result confirming a conjecture due to Erdös, Faudree, Rousseau and Schelp that for and in the case where . [Copyright &y& Elsevier]

Abstract: Let denote a tree of order and a wheel of order . In this paper, we show the Ramsey numbers for , where if , if or and , and otherwise; for . [Copyright &y& Elsevier]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest positive integer n such that for any graph G of order n, either G contains G1 or the complement of G contains G2. Let Sn denote a star of order n and Wm a wheel of order m+1. This paper shows that R(Sn,W6)=2n+1 for n≥3 and R(Sn,Wm)=3n-2 for m odd and n≥m-1≥2. [Copyright &y& Elsevier]

A graph G is 3-domination critical if its domination number \gamma is 3 and the addition of any edge decreases \gamma by 1. It was proved by Favaron et al. that α ≤ δ + 2 for any connected 3-domination critical graph. Denote byτ (G) the toughness of a graph G. Recently Chen et al. conjectured that a connected 3-domination critical graph G is Hamilton-connected if and only if τ(G) > 1 and showed the conjecture is true when α ≤ δ. In this paper, by using a closure operation defined by Bondy and Chva´tal, we show the conjecture is true whenα = δ + 2. [Copyright &y& Elsevier]

Abstract For given graphs H 1 ,... , H k , k ≥ 2 , the k -color Ramsey number R (H 1 ,... , H k) is the smallest integer N such that every k -coloring of the edges of a complete graph K N contains a monochromatic copy of H i colored in i , for some i with 1 ≤ i ≤ k. Let C ℓ , K 1 , m and P n denote a cycle of length ℓ , a star of order m + 1 and a path of order n , respectively. In this paper, it is shown that R (C 4 , K 1 , m , P n) ≤ m + n − 1 + ⌈ m + n − 2 ⌉ for all m , n ≥ 2 and R (C 4 , K 1 , m , P n) ≤ m + n − 2 + ⌈ m + n − 2 ⌉ if m + n = ℓ 2 + 3 and ℓ ≥ 1. Moreover, by discussing the local structure of the polarity graph whose vertices are points in the projective plane over Galois fields, we show that the two upper bounds can be attained for some special m and n. These results also extend some known results on R (C 4 , K 1 , m) obtained by Parsons in 1975 and by Zhang et al. recently. [ABSTRACT FROM AUTHOR]

A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai k -coloring is a Gallai coloring that uses at most k colors. For an integer k ≥ 1 , the Gallai–Ramsey number G R k (H) of a given graph H is the least positive integer N such that every Gallai k -coloring of the complete graph K N contains a monochromatic copy of H. Let C m denote the cycle on m ≥ 4 vertices and let Θ m denote the family of graphs obtained from C m by adding an additional edge joining two non-consecutive vertices. We prove that G R k (Θ 2 n + 1) = n ⋅ 2 k + 1 for all k ≥ 1 and n ≥ 3. This implies that G R k (C 2 n + 1) = n ⋅ 2 k + 1 all k ≥ 1 and n ≥ 3. Our result yields a unified proof for the Gallai–Ramsey number of all odd cycles on at least five vertices. [ABSTRACT FROM AUTHOR]