摘要
设图G是n阶的单图,Gc是它的补图.用a(G)表示图G的代数连通度.在很多文献中,已经研究了邻接谱半径的Nordhaus-Gaddum型的界的问题.本文进一步探讨了代数连通度的Nordhaus-Gaddum型的界.得到:对树和其他一些图,a(G)+a(Gc)≥1成立,并刻画了等式成立时的图的特征.根据这些结果,最后提出这样一个猜想:对n阶的单图G,有a(G)+a(Gc)≥1.
Let G be a simple graph with n vertices and G＇be its complement graph. Let a（G） be the algebraic connectivity of G. The bound for the spectrum of the Nordhaus-Gaddum type has been studied in many papers while this paper, the bound for the algebraic connectivity of the Nordhaus-Gaddum type is observed. For the trees and some other graphs, a（G） ＋a（G＇） ≥1 is obtained and the graphs which achieve the bound is also characterized. As a result, the following conjecture is given： Let G be a graph of order n, then a（G）＋a（G）≥l.
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2009年第6期616-619,共4页
Journal of Zhejiang University（Science Edition）
基金
Supported by NSFC(10671033)
The Natural Science Foundation of Nantong University(08Z003)
关键词
N—G型
代数连通度
界
Nordhaus-Gaddum type
algebraic connectivity
bound
