一些图的独立多项式的单峰型性质

论文摘要

图的独立集的研究是图论中最原始的问题之一,图论研究中的一些经典问题,如:棋盘问题(chess broad),图的匹配(matching)问题、着色(coloring)问题、cliques(团)、支配集(dominating sets)等都和独立集密不可分(例如:图G的匹配是其线图的独立集,图G的团是其补图的独立集);在编码学、计算机科学理论和网络理论等方面也都会涉及到图的独立集的问题。因此图的独立集的研究既有重要的理论意义又有着广泛的实际应用,也正因为如此,对图的独立集的研究一直非常活跃。Erd(?)s和Moser等一批学者对此做了深入的研究。 本文主要来讨论一些图的独立多项式的单峰型性质。 第一章主要介绍了图的基本概念以及单峰型性质。 第二章主要证明了Levit和Mandrescu提出的猜想(以后称其为LM猜想):蜈蚣树(centipedes)的独立多项式只有实零点。 第三章在Levit和Mandrescu所研究的蜈蚣树的基础上,进一步研究毛毛虫树(caterpillars)、Vertebrate树的独立多项式的单峰型性质。 第四章主要讨论一类图的独立多项式的指标。

论文目录

• 摘要
• Abstract
• 目录
• 前言
• 第一章 基本概念
• 1.1 图的概念和基本性质
• 1.2 图的独立多项式及相关结论
• 1.3 单峰型性质
• 第二章 对Levit和Mandrescu的猜想的证明
• 2.1 与LM猜想相关的结论
• 2.2 证明LM猜想
• 第三章 道路和毛毛虫树的独立多项式的单峰型性质
• 3.1 道路和毛毛虫树的独立多项式的单峰型性质
• 3.2 注记
• 第四章 一类图的独立多项式的指标的推广
• 4.1 一类图的独立多项式指标
• 4.2 应用举例
• 参考文献
• 攻读硕士学位期间发表论文情况
• 论文创新点摘要
• 致谢
• 大连理工大学学位论文版权使用授权书