Search

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any graph G of order n, either G contains G1 or its complement G¯ contains G2. Let Pn,Sn and Tn denote a path, a star and a tree of order n, respectively. A generalized wheel, denoted by Ws,m, is the join of a complete graph Ks and a cycle Cm. In this paper, we show that R(Tn,Ws,4)=(n-1)(s+1)+1 for n≥3,s≥2 and R(Tn,Ws,5)=(n-1)(s+2)+1 for n≥3,s≥1. These generalize some known results on Ramsey numbers for a tree versus a wheel. [ABSTRACT FROM AUTHOR]

For two given graphs $$G_1$$ and $$G_2$$ , the planar Ramsey number $$PR(G_1,G_2)$$ is the smallest integer $$N$$ such that for any planar graph $$G$$ of order $$N$$ , either $$G$$ contains $$G_1$$ or the complement of $$G$$ contains $$G_2$$ . Let $$K_m$$ denote a complete graph of order $$m$$ and $$W_n$$ a wheel of order $$n+1$$ . In this paper, we determine all planar Ramsey numbers $$PR(K_m,W_n)$$ . [ABSTRACT FROM AUTHOR]

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]

We consider proper edge colorings of a graph G using colors of the set { 1 , … , k } . Such a coloring is called neighbor sum distinguishing if for any u v ∈ E ( G ) , the sum of colors of the edges incident to u is different from the sum of the colors of the edges incident to v . The smallest value of k in such a coloring of G is denoted by ndi Σ ( G ) . Let mad ( G ) and Δ ( G ) denote the maximum average degree and the maximum degree of a graph G , respectively. In this paper we show that, for a graph G without isolated edges, if mad ( G ) < 8 3 , then ndi Σ ( G ) ≤ max { Δ ( G ) + 1 , 7 } ; and if mad ( G ) < 3 , then ndi Σ ( G ) ≤ max { Δ ( G ) + 2 , 7 } . [ABSTRACT FROM AUTHOR]

Abstract: For two given graphs and , the planar Ramsey number is the smallest integer such that for any planar graph on vertices, either contains or its complement contains . Let denote a cycle of length and a complete graph of order . Sun, Yang, Lin and Song conjectured that and the conjecture was proved for . In this paper, it is shown that which confirms the conjecture for . [Copyright &y& Elsevier]

Abstract: A graph is 3-domination-critical (3-critical, for short), if its domination number is 3 and the addition of any edge decreases by 1. In this paper, we show that every 3-critical graph with independence number 4 and minimum degree 3 is Hamilton-connected. Combining the result with those in [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 271 (2003) 1–12; Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with , European Journal of Combinatorics 23 (2002) 777–784; Y.J. Chen, T.C.E. Cheng, C.T. Ng, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 308 (2008) (in press)], we solve the following conjecture: a connected 3-critical graph is Hamilton-connected if and only if , where is the toughness of . [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: 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 . In this paper, we show that for odd, and , which was conjectured by Surahmat, Baskoro and Tomescu. [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]

Abstract: Given two graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or its complement contains . Let denote a cycle of order and a wheel of order . In this paper, it is shown that for odd, and , and for odd and . [Copyright &y& Elsevier]