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

论文摘要

图的独立集的研究是图论中最原始的问题之一,图论研究中的一些经典问题,如:棋盘问题(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 应用举例

参考文献

攻读硕士学位期间发表论文情况

论文创新点摘要

致谢

大连理工大学学位论文版权使用授权书

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

论文摘要

论文目录

相关论文文献