关于图的独立多项式的研究

发布时间：2017-05-19 10:04

  本文关键词：关于图的独立多项式的研究，由笔耕文化传播整理发布。

【摘要】：图G的独立多项式I(G；x)=∑k=0α(G)sk·xk,表示基数为k的独立集数目,其中k：∈{1…,a(G)},α(G)是图G的极大独立集的数目.在本文中我们探讨独立多项式,(G；x)的一些重要性质,并得到以下结果：(1)对于树或者是单圈图,如果图G是围长g≥6(或者g≥5)和G≠qC7(或者G≠gK2)的良好覆盖图(非常良好覆盖图),其中g是任意正整数,有,(G;-1)=0.即对于图G,偶数阶独立集和奇数阶独立集的数目是相等的.(2)存在图序列G1,G2,…,Gn,…,使得|I(Gn+1；-1)|-|(Gn+1;-1)|=2n,n=1,2,….也就是说存在图序列,当圈秩数增加1时,图的偶数阶独立集与奇数阶独立集差的绝对值是以指数级增加的；另一方面,存在图序列H1,H2,…,Hn,使得|I(Hn;-1)|≤M(M0),n=1,2,….即存在图序列,当圈秩数增加时,图的偶数阶独立集与奇数阶独立集数值差不大于数M.(3)对于平面基图G(没有垂点),当β(G)=2时,证明了|I(G;-1)|≤2β(G)-1.证明了Levit和Mandrescu提出的猜想：对任意满足|q|≤2β的正整数β和整数q,存在连通图G,有圈秩数β(G)=β和I(G；-1)=q.
【关键词】：独立集 图的独立多项式 有界性 单调性 良好覆盖图
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O174.14;O157.5
【目录】：

• 中文摘要6-7
• 英文摘要7-11
• 第一章 前言11-22
• §1.1 引言11-13
• §1.2 图的独立多项式的基本性质13-22
• 第二章 图的构造22-34
• §2.1 圈秩数β(G)≤2的图的独立多项式23-31
• §2.2 圈秩数β(G)≥3的图的独立多项式31-34
• 第三章 总结34-36
• §3.1 总结34-36
• 参考文献36-38
• 致谢38

【相似文献】

中国期刊全文数据库 前10条

1 徐新萍;;独立集的度和与图的哈密尔顿性[J];运筹学学报;2006年03期

2 李国君，刘振宏;3－连通正则无爪图的Hamilton圈[J];数学进展;1996年01期

3 林育青;关于简单图的独立集多项式[J];东北重型机械学院学报;1997年02期

4 徐新萍;;哈密尔顿性和部分平方图的独立集(英文)[J];南京师大学报(自然科学版);2006年02期

5 赵树峰;赵小玲;;树图的r-色独立集划分问题[J];漯河职业技术学院学报;2007年02期

6 崔丽丽;方奇志;孔亮;;独立集对策的核心稳定性[J];自然科学进展;2008年04期

7 江蓉;王守中;;一类三角系统的匹配数与点独立集数[J];西南师范大学学报(自然科学版);2009年01期

8 徐新萍;;哈密尔顿性和部分平方图的独立集[J];数学的实践与认识;2009年10期

9 王蒙;田双亮;;若干图的r-色独立集划分问题[J];西北民族大学学报(自然科学版);2011年02期

10 林翠琴，居余马;独立集上最小最大比值和最小极差比值问题的算法[J];清华大学学报(自然科学版);1994年06期

中国重要报纸全文数据库 前2条

1 麻玉秀;独立集采人：挖掘聚众效应下的财富[N];中国经营报;2006年

2 本报记者　 张迪;独立集采人组织家装团购月入万元[N];北京日报;2006年

中国博士学位论文全文数据库 前4条

1 张海良;关于图的两类多项式及相关指数的研究[D];华东师范大学;2013年

2 徐新萍;图的哈密尔顿性的若干结果[D];南京师范大学;2003年

3 宋文兔;网络分解在网络编码中的应用[D];北京大学;2012年

4 王世英;图的匹配的若干结构性问题[D];郑州大学;2000年

中国硕士学位论文全文数据库 前10条

1 何盼英;关于图的独立多项式的研究[D];华东师范大学;2016年

2 景伟;几类图的匹配、点独立集、点极大独立集的计数[D];华中师范大学;2009年

3 王华平;点独立集度和的几个结果[D];江西师范大学;2002年

4 邹玲平;格子系统的独立集的计数[D];厦门大学;2007年

5 朱志峰;一些图的独立多项式的单峰型性质[D];大连理工大学;2005年

6 徐敏;关于图的Hamilton性的几个新结果[D];南京师范大学;2002年

7 王金杰;基于独立集求解图着色问题[D];华中科技大学;2013年

8 续晓欣;Q0-1规划模型下最大团、最大加权独立集问题的研究[D];太原理工大学;2006年

9 纪乃丹;图的独立集多项式和Clar覆盖多项式的转移矩阵计算[D];兰州大学;2006年

10 李树花;关于κ-匹配和κ-独立集的极值多联苯链及一些和图的点PI指标[D];新疆师范大学;2010年

  本文关键词：关于图的独立多项式的研究，由笔耕文化传播整理发布。

，

本文编号：378365