图的Nordhaus-Gaddumm型的代数连通度的界

• 作者: 吕嘉钧 吕大梅 杜娟
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: N-G型 代数连通度 界
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 616-619
• 页数: 4页
• 分类号: O157.5
• 字数: 1821字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2009.06.003

摘要

设图G是n阶的单图,Gc是它的补图.用a(G)表示图G的代数连通度.在很多文献中,已经研究了邻接谱半径的Nordhaus-Gaddum型的界的问题.本文进一步探讨了代数连通度的Nordhaus-Gaddum型的界.得到:对树和其他一些图,a(G)+a(Gc)≥1成立,并刻画了等式成立时的图的特征.根据这些结果,最后提出这样一个猜想:对n阶的单图G,有a(G)+a(Gc)≥1.