Search

The planar Ramsey number PR ( H 1 , H 2 ) is the smallest integer n such that any planar graph on n vertices contains a copy of H 1 or its complement contains a copy of H 2 . It is known that the Ramsey number R ( C 4 , K 7 ) = 22 . The planar Ramsey numbers PR ( C 4 , K l ) for l ≤ 6 are known. In this paper we show that PR ( C 4 , K 7 ) = 20 .

The planar Ramsey number PR(H"1,H"2) is the smallest integer n such that any planar graph on n vertices contains a copy of H"1 or its complement contains a copy of H"2. It is known that the Ramsey number R(K"4-e,K"5)=16. The planar Ramsey numbers PR(K"4-e,K"3)=7 and PR(K"4-e,K"4)=10 are known. In this paper we show that PR(K"4-e,K"5)=14.

Harary and Kovacs [Smallest graphs with given girth pair, Caribbean J. Math. 1 (1982) 24-26] have introduced a generalization of the standard cage question-r-regular graphs with given odd and even girth pair. The pair (@w,@e) is the girth pair of graph G if the shortest odd and even cycles of G have lengths @w and @e, respectively, and denote the number of vertices in the (r,@w,@e)-cage by f(r,@w,@e). Campbell [On the face pair of cubic planar graph, Utilitas Math. 48 (1995) 145-153] looks only at planar graphs and considers odd and even faces rather than odd and even cycles. He has shown that f(3,@w,4)[email protected] and the bounds for the left cases. In this paper, we show the values of f(r,@w,@e) for the left cases where (r,@w,@e)@?{(3,3,@e),(4,3,@e),(5,3,@e), (3,5,@e)}.

Calculating the crossing number of a given graph is, in general, an elusive problem. As Garey and Johnson have proved, the problem of determining the crossing number of an arbitrary graph is NP-complete (Crossing number is NP-complete, SIAM J. Alg. Disc. Meth. 4 (1983) 312-316). The crossing numbers of very few families of graphs are known exactly. Richter and Salazar (The crossing number of P(N,3), Graphs and Combinatorics 18 (2) (2002) 381-394) have studied the crossing number of the generalized Petersen graph P(n,3) and proved that cr(P(3h,3))=h(h>=4); cr(P(3h+1,3))=h+3(h>=3); cr(P(3h+2,3))=h+2(h>=3). In this paper, we study the crossing number of the circulant graph C(n;{1,3}) and prove that cr(C(n;{1,3}))[email protected]?n/[email protected]?+nmod3(n>=8).

Investigation of the crossing number of graphs is a classical but very difficult problem. The exact value of the crossing number is known only for a few specific families of graphs. In this paper we extend a recent result from Bokal on the crossing number of K1,m□Pn, and prove that cr(K2,m□Pn)=2n⌊m2⌋⌊m−12⌋.