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

10.29252/asta.4.1.1

Abstract

Let $G$ be a graph with eigenvalues $\lambda_1(G)\geq\cdots\geq\lambda_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 $n\leq12$ and $\lambda_1(G)\geq0$, $\lambda_2(G)\geq0$ and $\lambda_3(G)<0$. We obtain that there are exactly $1575$ connected graphs $G$ on $n\leq12$ vertices with $\lambda_1(G)>0$, $\lambda_2(G)>0$ and $\lambda_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.