关于图的若干参数的研究

发布时间：2017-05-18 14:06

  本文关键词：关于图的若干参数的研究，，由笔耕文化传播整理发布。

【摘要】：令G是阶为n的简单无向图,A(G)是G的邻接矩阵,D(G)=diag(d1,d2,···,dn)是其顶点的度对角阵.那么Q(G)=A(G)+D(G)称为G的无符号拉普拉斯矩阵.G的无符号拉普拉斯谱半径q1(G)就是Q(G)的最大特征值.给定一个不含孤立点的图G=(V,E),G的一个全控制集S称为定位全控制集,如果对V-S中任何两个不同的顶点u和v,都有N(u)∩S N(v)∩S,其中N(u)={w|uw∈E};S称为区分全控制集,如果对V中任何两个不同的顶点u和v,都有N[u]∩S N[v]∩S,其中N[u]=N(u)∪{u}.G的定位全控制数γL t(G)(或者区分全控制数γD t(G)),是G中所含点数最少的定位全控制集(或者是区分全控制集)中的点数.图G的顶点子集S是G的一个2-控制集,如果G中不在S中的每个点都和S中至少两个点相邻.G的2-控制数γ2(G),是G中所含点数最少的2-控制集中的点数.G的毁灭数a(G),定义为最大的正整数k使得G的非减度序列中的前k项之和最多是G的边数.在第三章,我们首先研究了一般图的无符号拉普拉斯谱半径的上下界.其次,对于给定的非正则图G,我们利用G的直径d和顶点数n给出了2?-q1(G)的下界,并且利用最大度?、最小度δ以及顶点数n等参数给出了q1(G)-4m n的下界.另外,对于k连通的非正则图G,我们利用最大度?、最小度δ、顶点数n、边数m以及连通度κ给出了2?-q1(G)的下界.在第四章,我们首先利用图的顶点数n、直径d和叶子数l给出了树图的区分全控制数的上下界;我们还刻画了达到这些界的树的结构.其次,对于单圈图G,我们利用它的顶点数n、支撑点数s、强支撑点数s1以及叶子数l给出了定位和区分全控制数的极值,并刻画了极图.在第五章,我们研究了树的定位全控制数与毁灭数的关系.最后,我们用毁灭数给出了单圈图的2-控制数的上界,从而部分地解决了有关一般图的2-控制数和毁灭数的一个猜想.
【关键词】：无符号拉普拉斯谱半径 定位全控制 区分全控制 2-控制数 毁灭数
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-8
• 主要符号对照表8-9
• 第1章 基本概念9-13
• 第2章 概述13-23
• 2.1 研究背景和研究动态13-22
• 2.1.1 无符号拉普拉斯谱半径14-17
• 2.1.2 图的定位和区分全控制数17-20
• 2.1.3 图的毁灭数20-22
• 2.2 本文结构及主要研究内容22-23
• 第3章 非正则图的无符号拉普拉斯谱半径23-41
• 3.1 一般图的情形23-26
• 3.2 非正则图的无符号拉普拉斯谱半径26-33
• 3.3 k连通非正则图的无符号拉普拉斯谱半径33-41
• 第4章 图的定位和区分全控制数41-64
• 4.1 树图的区分全控制集41-54
• 4.1.1 树图的区分全控制数的下界41-47
• 4.1.2 树图的区分全控制数的上界47-54
• 4.2 单圈图的定位及区分全控制集54-64
• 4.2.1 单圈图的定位全控制数54-58
• 4.2.2 单圈图的区分全控制数58-64
• 第5章 毁灭数和两类控制数的关系64-78
• 5.1 树的定位全控制数和毁灭数的关系64-71
• 5.1.1 术语64-65
• 5.1.2 已知结果65
• 5.1.3 主要结论65-71
• 5.2 关于图的 2-控制数和毁灭数的一个猜想71-78
• 5.2.1 已知结果72-73
• 5.2.2 主要结论73-78
• 第6章 结论78-79
• 6.1 本文工作总结78
• 6.2 未来研究展望78-79
• 参考文献79-84
• 致谢84-86
• 个人简历、在学期间发表的学术论文与研究成果86

【参考文献】

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

1 李瑞林;施劲松;董炳灿;;给定独立数的双圈图的最大拟拉普拉斯谱半径(英文)[J];华东师范大学学报(自然科学版);2011年03期

  本文关键词：关于图的若干参数的研究，由笔耕文化传播整理发布。

本文编号：376243