Paths, Cycles and Wheels

sin Graphs without Antitriangle

Stanisl/aw P. Radziszowski and Jin Xia

Department of Computer Science
Rochester Institute of Technology

A

Rochester, NY 14623

bstract. We investigate paths, cycles and wheels in graphs with indepenl
s
dence number at most 2, in particular we prove theorems characterizing al
uch graphs which are hamiltonian. The values of Ramsey numbers of the
lform R (G , K ), for G being a path, a cycle or a wheel, are known to be equa
3
to 2n (G ) - 1, except some small cases. In this paper we derive and count all

1

the critical graphs for these Ramsey numbers.

. Notation and Previous Work

For any graph F , V (F ) and E (F ) will denote the vertex and edge sets of the graph F , also let

c
n (F ) = | V (F ) | and e (F ) = | E (F ) | . The graph F`` denotes the complement of F . A graph F will be alled a (G , H )-good graph, if F does not contain G and F`` does not contain H . Any (G , H )-good s
t
graph on n vertices will be called a (G , H , n )-good graph. The Ramsey number R (G , H ) is defined a he smallest integer n such that no (G , H , n )-good graph exists. Any graph is called a critical graph for r
a
the Ramsey number R (G , H ) if it is (G , H , R (G , H ) - 1)-good. When the graph F is fixed, then fo ny vertex x ?V (F ), G and H will denote the graphs induced by the neighbors of the vertex x or by x x
i i ,
a
all the vertices disconnected from x , respectively. P is a path on i vertices, C is a cycle of length i nd W is a wheel with i -1 spokes, i.e. a graph formed by some vertex x , called a hub of the wheel, i
i -1 i -
j
connected to all vertices of some cycle C , called a rim . 2K is the graph formed by two vertex dis oint copies of K . For notational convenience we define C = K for 1 ? i ? 2.
i i i

3 a
w

In this paper most of the considered graphs are (T , K , n )-good for T being a path, a cycle, or heel. It is easy to see that if F is any (T , K , n )-good graph and x is a vertex in V (F ) of degree deg (x ) = d , then: 3

(a) if T = C then G is a (P , K , d )-good graph,
i +1 x i 3
i +1 x i 3 ,

a

(b) if T = W then G is a (C , K , d )-good graph

nd H is a complete graph K . Observe that any graph without independent sets of size three and w x n - d - 1
ith more than one component is a vertex disjoint union of two cliques. We also note that the whole e
f
contents of this paper can be seen as a study of paths, cycles and wheels in the complements of triangl ree graphs.

The value of the Ramsey number R (P , K ) = 2i - 1 is a consequence of a well known theorem by i 3
3 d
g
Chva?tal [3]. An interesting general related result in [2] says that R (G , K ) = 2i -1 for any connecte raph G of order i ? 4 with at most (17i + 1)/15 edges, which obviously applies to the cases of paths and cycles, but no wheels. Burr and Erdo..s [1] showed that R (W , K ) = 2i - 1 for all i ? 6, and the i 3
5 3 d
c
tables by Clancy [4] include the special value of R (W , K ) = 11. McKay and Faudree [5] generated an ounted by computer all of the critical graphs for the Ramsey numbers R (W , K ) for all j ? 11, and our j 3 d
t
proofs confirm their results. In two recent papers Sidorenko studied the general case: in [7] he showe hat for any graph G without isolated vertices we have R (G , K ) ? 2e (G ) + 1, which improved on his 3 aprevious result in [6], where he also formulated an interesting conjecture that for any graph G there is