文档介绍：第卷第期经济数学
年月
图的点覆盖数与其谱半径‘
袁西英
上海理工大学理学院,上海,
束金龙
华东师范大学数学系,上海,
摘要本文讨论图的点覆盖数与图的谱半径的关系,利用特征向量的技巧得到由图的谱
半径所确定的关于图的点覆盖数的紧的界
关键词图,语半径,点覆盖数,点无关数
引言
设,是一个阶简单无向图无环,无重边,其中,⋯,。为顶点集,
,,⋯,二为边集记,。,为顶点,的度,则矩阵一称为图的
矩阵,其中一二,,。,⋯,。,,是,邻接矩阵·对于的一些
重要的性质以及对此研究的重要性可参见文献「〕,「〕等图的谱半径定义为
的最大特征根,记为爪,或者简记作热
对图的矩阵的研究之所以重要,其中一个原因是可以用其特征值来估计图的许
多不变量,如复杂度即著名的矩阵树理论,连通度〕,直径「,带宽「〕等有些不变量的计
算是一的,而谱的计算仅涉及到线性方程组的求解本文建立了图的点覆盖
数和图的谱半径的关系,从而可以用图的谱半径对其点覆盖数做出估计
先介绍点覆盖集和点独立集的概念〕
定义集合二,如果中的任何一边都至少有一个端点属于,则称为的一个
点覆盖集,中包含顶点最少的点覆盖集为最小点覆盖集,其点数记为,称为图的点覆盖
数
定义集合里,如果中的任意两点在中不相邻,则称为的一个点独立集
中包含顶点最多的点独立集称为最大点独立集,其点数记为月,称为图的点独立数
记阶简单图的最小点覆盖数和最大点独立数分别为和月,有川月
由此可见,求一个图的最大的点独立集的问题和求它的最小点覆盖集的问题是等价的对
于一般图,寻求月是一个困难问题,文献「中给出了点独立数的一个下界
引理〕设,,班是的点独立数,则
八。、、,
户山,匕鹿反二不万
上海理工大学青年科研基资资助项目
收稿日期一一
经济数学第卷
等式成立当且仅当是点不交的完全图的并
下面的占,乙分别表示阶连通图的最小度和点连通度,文献「〕给出了下面两个界
,, 一、、, 、。。。, ‘
引理若“之言△,则月二八
引理若对任意两个不相邻点,,满足试。峨。,则月二△
设二,,⋯,尸是维列向量我们用,任表示点,,,在图相邻接
由矩阵的定义知
了一万,一,,
即少“

从而是一个半正定对称奇异矩阵,故其特征根全部为非负实数记,,⋯,是
维全列向量,有从而可以将的特征根按非降序排列为
产几全几全⋯全久。
下面我们主要探讨产和的关系
主要结论
首先给出矩阵论中我们熟知的一个结果
引理
产笙丛丝塑笙
艺尸,一。,任律,荆
定理,是一个简单连通图,,则其谱半径产和点覆
盖数有下列三个关系式成立
产一一产二,

全兰,
产
、,
夕口于士七儿一—。
产
证明设是的一个最小点覆盖集,〔」是由中顶点形成的的诱导子图,记
, ,、一
为‘,则有‘,‘二万以一八从阴
,。,二、、、。。,、,、
】乙行乙‘乙阴一下一
乙
若‘任口,则‘的两个端点均在中若己〔‘,由最小点覆盖集的定义知‘有
且只有一个端点在中,构造向量任”,其分量满足
一当,任时,
一当,任时
从而,
了,二一十一一
“二, 一