几类树的独立多项式的对数凹性

发布时间：2018-04-22 17:27

本文选题：树 + 单峰性　；参考：《江苏师范大学》2017年硕士论文

【摘要】：图的独立多项式是代数图论研究中的一个重要组成部分,对其单峰型性质的研究是代数图论中的一个热点问题.1987年,Erd?os等人猜想任意一棵树或者森林的独立多项式都是单峰的.这个猜想吸引了许多图论研究者的兴趣,虽然已取得了部分进展,但是至今仍未解决.本文通过对独立多项式进行因式分解,将复合图的独立多项式分解为几个多项式因子的乘积来研究,进而证明复合图的独立多项式的对数凹性,从而为Erd?os等人的上述猜想,提供了更多的例子.具体内容如下:第一章图论的基本概念以及独立多项式的已知结果.第二章本章仿照蜈蚣图,定义了新的复合图,取名为广义蜈蚣图.通过求解递推关系式,给出了其独立多项式的显式表达.进一步,考虑了树图中三类特殊的广义蜈蚣图,并证明了它们的独立多项式都是对数凹的,从而是单峰的.第三章本章定义了一类树,取名为双灯树.利用某类无爪图,给出了双灯树的独立多项式的表达式,并证明了其仅有实零点,从而是对数凹和单峰的.第四章总结。
[Abstract]:The independent polynomial of a graph is an important part in the study of algebraic graph theory, and the study of its unimodal property is a hot issue in the theory of algebraic graph. In 1987, Erdfos et al assumed that the independent polynomial of any tree or forest is unimodal. This conjecture has attracted the interest of many graph theorists. Although some progress has been made, it has not been solved. In this paper, by factorizing independent polynomials, the independent polynomials of complex graphs are decomposed into the product of several polynomial factors, and the logarithmic concave of independent polynomials of composite graphs is proved, which is the conjecture of Erd?os et al. More examples are provided. The main contents are as follows: the first chapter is the basic concept of graph theory and the known results of independent polynomials. In the second chapter, a new compound graph is defined, named the generalized centipede graph, following the centipede graph. The explicit expression of its independent polynomial is given by solving the recursive relation. Furthermore, three special generalized centipede graphs in tree graphs are considered, and it is proved that their independent polynomials are logarithmic concave and thus unimodal. The third chapter defines a kind of tree, named double lamp tree. In this paper, we give the expression of independent polynomial of double lamp tree by using some kind of claw free graph, and prove that it has only real zero point, so it is logarithmic concave and unimodal. Chapter IV Summary.
【学位授予单位】：江苏师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】