A note on the Nordhaus-Gaddum type inequality to the second largest eigenvalue of a graph

Applicable Analysis and Discrete Mathematics

article

Nair Abreu¹  André E. Brondani¹  Leonardo de Lima²  Carla Oliveira³ 

[1] Institution Federal Fluminense University, Instituto de Cincias Exatas Departamento de Matemtica;Federal University of Rio de Janeiro;ENCE

关键词: Nordhaus-Gaddum problem;    adjacency matrix;    upper bound;    second largest eigenvalue;   

DOI  :  10.2298/AADM1701123A

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

Let G be a graph on n vertices and G its complement. In this paper, weprove a Nordhaus-Gaddum type inequality to the second largest eigenvalueof a graph G, λ2(G),λ2(G) + λ2(G) ≤ −1 + rn22− n + 1,when G is a graph with girth at least 5. Also, we show that the bound aboveis tight. Besides, we prove that this result holds for some classes of connectedgraphs such as trees, k−cyclic, regular bipartite and complete multipartitegraphs. Based on these facts, we conjecture that our result holds to anygraph.

【 授权许可】

Unknown