Search

Given two graphs $$G_1$$ and $$G_2$$ , the Ramsey number $$R(G_1, G_2)$$ is the smallest integer $$N$$ such that, for any graph $$G$$ of order $$N$$ , either $$G_1$$ is a subgraph of $$G$$ , or $$G_2$$ is a subgraph of the complement of $$G$$ . We consider the case that $$G_1$$ is a cycle and $$G_2$$ is a (generalized) wheel. We expand the knowledge on exact values of Ramsey numbers in three directions: large cycles versus wheels of odd order; large wheels versus cycles of even order; and large cycles versus generalized odd wheels. [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 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, it is shown that . [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: A graph G is 3-domination critical if its domination number is 3 and the addition of any edge decreases by 1. Let G be a 3-domination critical graph with toughness more than one. It was proved that G is Hamilton-connected for the cases [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with , Discrete Math. 271 (2003) 1–12] and [Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with , European J. Combin. 23 (2002) 777–784]. In this paper, we show G is Hamilton-connected for the case . [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 m and a complete graph of order . It was conjectured that for and . We show that and , and the latter result confirms the conjecture in the case when . [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]

Abstract: Let be a graph. A subset of is called a dominating set if each vertex of has at least one neighbor in . The domination number equals the minimum cardinality of a dominating set in . A minus dominating function on is a function such that for each , where is the closed neighborhood of . The minus domination number of is . It was incorrectly shown in [X. Yang, Q. Hou, X. Huang, H. Xuan, The difference between the domination number and minus domination number of a cubic graph, Applied Mathematics Letters 16 (2003) 1089–1093] that there is an infinite family of cubic graphs in which the difference can be made arbitrary large. This note corrects the mistakes in the proof and poses a new problem on the upper bound for in cubic graphs. [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 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 . It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that for even , and . In this paper, we confirm the conjecture for . [Copyright &y& Elsevier]

In this paper, we study the upper size Ramsey number u ( G 1 , G 2 ) , defined by Erdős and Faudree, as well as the star-critical Ramsey number r ∗ ( G 1 , G 2 ) , defined by Hook and Isaak. We define Ramsey-full graphs and size Ramsey good graphs, and perform a detailed study on these graphs. We generalize earlier results by determining u ( n K k , m K l ) and r ∗ ( n K k , m K l ) for k , l ≥ 3 and large m , n ; u ( C n , C m ) for m odd, with n > m ≥ 3 ; and r ∗ ( C n , C m ) for m odd, with n ≥ m ≥ 3 and ( m , n ) ≠ ( 3 , 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 G of order N , either G contains G 1 as a subgraph or the complement of G contains G 2 as a subgraph. Let T n be a tree of order n , S n a star of order n , and F m a fan of order 2 m + 1 , i.e., m triangles sharing exactly one vertex. In this paper, we prove that R ( T n , F m ) = 2 n − 1 for n ≥ 3 m 2 − 2 m − 1 , and if T n = S n , then the range can be replaced by n ≥ max { m ( m − 1 ) + 1 , 6 ( m − 1 ) } , which is tight in some sense. [ABSTRACT FROM AUTHOR]