tailieunhanh - Báo cáo toán học: "Maximum Independent Sets in Certain Powers of Odd Cycles"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Maximum Independent Sets in Certain Powers of Odd Cycles. | Maximum Independent Sets in Certain Powers of Odd Cycles Tom Bohman Ron Holzman t Venkatesh Natarajan Ỉ Submitted Jan 2 2008 Accepted Jul 6 2009 Published Jul 24 2009 Mathematics Subject Classification 05C38 05C69 Abstract We give a complete classification of all maximum independent sets in powers of odd cycles of the form Cd2d 1- 1 Introduction Consider the following natural packing problem How many d-dimensional cubes of side length 2 can we pack into a d-dimensional torus with a fixed odd side length This problem can be formulated in terms of graph products as follows. If G1 V1 E1 and G2 V2 E2 are graphs then let G1 X G2 be the graph with vertex set V1 X V2 and an edge between distinct vertices u1 u2 and v1 v2 if and only if Ui vi or ui vi G Ei for i 1 2. The graph power Gd is then the product of G with itself d times. A packing of cubes of side length 2 in the d-dimensional torus of side length 2n 1 corresponds to an independent set in C2n 1. This correspondence between packings of cubes in the torus and independent sets in powers of odd cycles was first noted by Baumert et al 1 . Let a G denote the independence number of graph G . the maximum size of an independent set in G. The independence numbers of the powers of odd cycles are also related to a central open question on the Shannon capacities of graphs. The Shannon capacity of the graph G is defined as c G sup a Gd 1 d d Department of Mathematical Sciences Carnegie Mellon University Pittsburgh USA. Supported in part by NSF grant DMS 0401147. E-mail tbohman@ Department of Mathematics Technion-Israel Institute of Technology Haifa Israel. Research supported by the Fund for the Promotion of Research at the Technion and by the P. and E. Nathan Research Fund. E-mail holzman@ Department of Mathematical Sciences Carnegie Mellon University Pittsburgh USA. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N26 1 and gives a measure of optimal zero-error performance of an associated .