Small graphs with exactly two non-negative eigenvalues

Document Type : Research Paper

Authors

1 Department of Mathematics, Marvdasht Branch, Islamic Azad University, Marvdasht, Iran

2 Department of Mathematics, College of Sciences, Shiraz University, Shiraz, 71457-44776, Iran

Abstract

Let G be a graph with eigenvalues λ1(G)λn(G). In this paper we find all simple graphs G such that G has at most twelve vertices and G has exactly two non-negative eigenvalues. In other words we find all graphs G on n vertices such that n12 and λ1(G)0, λ2(G)0 and λ3(G)<0. We obtain that there are exactly 1575 connected graphs G on n12 vertices with λ1(G)>0, λ2(G)>0 and λ3(G)<0. We find that among these 1575 graphs there are just two integral graphs.

Keywords


[1] M.R. Oboudi, Bipartite graphs with at most six non-zero eigenvalues, Ars Mathematica Contemporanea 11 (2016) 315–325.
[2] M.R. Oboudi, Characterization of graphs with exactly two non-negative eigenvalues, Ars Mathematica Contemporanea 12 (2017) 271–286.
[3] M.R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra and its Applications 503 (2016) 164–179
[4] M. Petrovi´c, Graphs with a small number of nonnegative eienvalues, Graphs and Combinatorics 15 (1999) 221–232.
[5] J. H. Smith, Symmetry and multiple eigenvalues of graphs, Glas. Mat., Ser. III 12 (1977) No. 1, 3-8.