TAILIEUCHUNG - Báo cáo toán học: "Operations on Well-Covered Graphs and the Roller-Coaster Conjecture"

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.

• Báo cáo khoa học
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• Nghiên cứu khoa học
• Phương pháp nghiên cứu khoa học
• Bài giảng Phương pháp nghiên cứu khoa học
• Báo cáo nghiên cứu khoa học
• Trình bày báo cáo nghiên cứu khoa học
• Văn phong sử dụng trong báo cáo khoa học
• Báo cáo khoa học công nghệ
• Đề tài nghiên cứu khoa học
• Nghiên cứu công nghệ làm phân vi sinh
• Báo cáo nghiên cứu phân vi sinh
• Báo cáo tình hình nghiên cứu khoa học
• Mẫu Báo cáo thực hiện nghiên cứu
• Trình bày Báo cáo thực hiện nghiên cứu
• Nội dung Báo cáo thực hiện nghiên cứu
• Hình thức Báo cáo thực hiện nghiên cứu
• Biên bản nghiên cứu khoa học
• Báo cáo khoa học và kỹ thuật
• Đề tài nghiên cứu khoa học y khoa
• Báo cáo nghiên cứu cấp nhà nước
• Nghiên cứu chất lượng chế phẩm thuốc
• Báo cáo nghiên cứu công nghệ sinh học
• Đề tài nghiên cứu thuốc sâu sinh học
• Báo cáo khoa học kỹ thuật
• Báo cáo quản lý chất thải sinh hoạt
• Báo cáo khoa học môi trường
• Nghiên cứu khoa học về môi trường
• Báo cáo nghiên cứu vệ sinh môi trường
• Nghiên cứu tình hình nhiễm độc Cadimi
• Báo cáo chế phẩm sinh học
• Báo cáo nghiên cứu ứng dụng sinh học
• Cách viết báo cáo khoa học
• Quy trình nghiên cứu khoa học
• Báo cáo kết quả nghiên cứu
• báo cáo khoa học
• tuyển tập báo cáo khoa học
• báo cáo ngành toán học
• báo cáo ngành vật lý
• báo cáo ngành chăn nuôi
• Nghiên cứu công nghệ phôi vô tính
• Báo cáo nghiên cứu nông nghiệp
• Báo cáo công nghệ xử lý chất thải
• Báo cáo nghiên cứu khoa học công nghệ
• Kết quả nghiên cứu lúa lai
• Cây lương thực
• Cây thực phẩm
• Một số nguyên tắc nghiên cứu khoa học
• Tiêu chuẩn báo cáo nghiên cứu khoa học
• Nguyên tắc báo cáo khoa học
• Báo cáo nghiên cứu công trình
• Nghiên cứu độ rỗng trong đá chứa dầu khí
• Nghiên cứu công nghệ UV–Fenton
• Nghiên cứu công nghệ xử lý nước thải
• Đề tài y tế đảm bảo an toàn người bệnh
• Báo cáo xây dựng hệ thống y tế
• Kỹ thuật viết báo cáo nghiên cứu
• Viết báo cáo nghiên cứu
• Báo cáo nghiên cứu
• khoa học
• Hình thức soạn thảo văn bản báo cáo
• Báo cáo nghiên cứu nước thải rượu
• Báo cáo công nghệ thiết bị UASB
• Đề tài công nghệ vi sinh
• luận văn mẫu
• người lính việt nam
• sau chiến tranh
• báo cáo ngành triết học
• báo cáo ngành lịch sử
• báo cáo ngành văn học