本文包括两方面的内容.第一部分研究简单图和平面图的无符号拉普拉斯谱半径的上界.如果一个图存在定向满足其最大出度△+不超过最大度△的一半,则通过估计图的半边路径(semi-edge walk)的个数,得到了该图的无符号拉普拉斯谱半径的一个新上界进而根据D.Goncalves对平面图边分解的结果,得到了平面图无符号拉普拉斯谱半径的一个新上界:第二部分研究简单图和平面图的平衡划分上界问题.给定一个图,通过该图的邻接矩阵,将平衡划分的边割数用矩阵表示,得到平衡划分的最小割的新上界:其中m和n分别是该图的边数和顶点数.进而对于平面图,得到当边数小于顶点数的两倍时,一定存在平衡划分使得边割数不超过顶点数.
本文来源: https://www.lw50.cn/article/859eb7323e4f899327f8a4dd.html