Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: THE INDEPENDENCE NUMBER OF DENSE GRAPHS WITH LARGE ODD GIRTH. | THE INDEPENDENCE NUMBER OF DENSE GRAPHS WITH LARGE ODD GIRTH James B. Shearer Department of Mathematics IBM . Watson Research Center Yorktown Heights NY 10598 JBS at Submitted January 31 1995 Accepted February 14 1995 Abstract. Let G be a graph with n vertices and odd girth 2k 3. Let the degree of a vertex v of G be d1 v . Let G be the independence number of G. Then we show a G 2- v Denley 1 . d1 v v2G k-1 k . This improves and simplifies results proven by AMS Subject Classification. 05C35 Let G be a graph with n vertices and odd girth 2k 3. Let di v be the number of points of degree i from a vertex v. Let a G be the independence number of G. We will prove lower bounds for a G which improve and simplify the results proven by Denley 1 . We will consider first the case k 1. We need the following lemma. Lemma 1 Let G be a triangle-free graph. Then G X d1 v 1 di v d2 v . v2G Proof. Randomly label the vertices of G with a permutation of the integers from 1 to n. Let A be the set of vertices v such that the minimum label on vertices at distance 0 1 or 2 from v is on a vertex at distance 1. Clearly the probability that A contains a vertex v is d1 v 1 d1 v d2 v . Hence the expected size of A is Xd1 v 1 d1 v d2 v . v2G Furthermore A must be an independent set since if A contains an edge it is easy to see that it must lie in a triangle of G a contradiction. The result follows at once. Typeset by A 5-TpX 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 N2 2 We can now prove the following theorem. Theorem 1. Suppose G contains no 3 or 5 cycles. Let d be the average degree of vertices of G. Then __ G ựnd 2. Proof. Since G contains no 3 or 5 cycles we have G di v consider the neighbors of v and G 1 d2 v consider v and the points at distance 2 from v for any vertex v of G. Hence G di v 1 di v d2 v di v 2 G by lemma 1 and the preceding remark . Therefore G 2 nd 2 or a G Iid 2 as claimed. This improves Denley s Theorems 1 and 2. It is sharp for the regular .
