图能量与边控制数关系的研究

作     者：王玲 

作者单位：中国矿业大学 

学位级别：硕士

导师姓名：王登银

授予年度：2017年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：图能量 特征值 最大度 点覆盖数 边控制数 

摘      要：对于一个无环无重边的简单图G,分别用V(G)和E(G)来表示图G的点集和边集.如果E(G)的子集F满足不在集合F中的任意一条边都至少与F中的一条边相邻接,则F称为G的边控制集.G的最小边控制集中所包含的边的条数称为图G的边控制数,记作θ(G).图G的能量ε(G)是G的所有特征值的绝对值之和.我们知道图的一个代数不变量——图的能量在图理论中占据重要地位,它在物理、化学等领域也有着广泛应用.Gutman将能量的概念推广到所有简单图,他定义简单图G的能量为ε(G)=(?),其中λ1,...,λn是G特征值.显然,如果我们能计算出一个图的特征值,我们就能立刻知道它的能量.但计算大规模矩阵的特征值是非常困难的,即使对于像邻接矩阵A(G)这样的(0,1)-对称矩阵也是十分困难的.于是,许多研究者便对某些图类建立了很多能量的上、下界来估计这一不变量.本文主要研究图G的能量与边控制数之间的关系.主要内容如下:第一章介绍与图的能量有关的研究背景和现状.第二章介绍了与本文有关的概念和已知的结论.第三章我们研究一种特殊情况——图的控制集为一条边时图的能量.第四章用先用图的边控制数证明了图能量的下界.如果G边控制数为θ的连通图,则ε(G)≥ 2θ,等号成立当且仅当G是完全二部图Kθ.θ.接着用图的边控制数证明了图能量的上界.ε(G)≤2θ(?)+(θ2-θ)((?)+ 1)Δ上界可达当且仅当G是由一条边连接两个K1,Δ-1的中心点得到的图形,其中Δ是G的顶点的最大度.