CAJ | 학술논문

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