Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Operations on Well-Covered Graphs and the Roller-Coaster Conjecture. | Operations on Well-Covered Graphs and the Roller-Coaster Conjecture Philip Matchett Emmanuel College Cambridge CB2 3AP ENGLAND pmatchet@ Submitted Feb 29 2004 Accepted Jun 15 2004 Published Jul 1 2004 MR Subject Classifications 05C69 05C75 Abstract A graph G is well-covered if every maximal independent set has the same cardinality. Let sk denote the number of independent sets of cardinality k and define the independence polynomial of G to be S G z V skzk. This paper develops a new graph theoretic operation called power magnification that preserves well-coveredness and has the effect of multiplying an independence polynomial by zc where c is a positive integer. We will apply power magnification to the recent Roller-Coaster Conjecture of Michael and Traves proving in our main theorem that for sufficiently large independence number a it is possible to find well-covered graphs with the last .17 a terms of the independence sequence in any given linear order. Also we will give a simple proof of a result due to Alavi Malde Schwenk and Erdos on possible linear orderings of the independence sequence of not-necessarily well-covered graphs and we will prove the Roller-Coaster Conjecture in full for independence number a 11. Finally we will develop two new graph operations that preserve well-coveredness and have interesting effects on the independence polynomial. 1 Introduction Let G V E be a graph without loops or multiple edges. A set of vertices W c V is called independent if no two vertices in W are adjacent. The independence number of G is the cardinality of the largest independent set denoted a G or just a. The independence sequence of G is the list s0 S1 s2 . . . sa where si is the number of independent sets of cardinality i and the independence polynomial S G z is the generating function of the independence sequence thus S G z V SiZ i 0 THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R45 1 Note that the degree of S G z is a G . Also by convention we set So 1.
