The Characterization of Graphs by Positive Inertia Index

Abstract

Let $G$ be a graph of order $n$. The number of positive eigenvalues of $G$ is called the positive inertia index of $G$ and denoted by $p(G)$. The minimum number of complete multipartite subgraphs in any complete multipartite graph edge decomposition of graph $G$, in which the edge-induced subgraph of each edge subset of the decomposition is a complete multipartite graph, is denoted by $ϵ(G)$. In this paper, we prove $ϵ(G)\ge p(G)$ for any graph $G$. Especially, if $ϵ(G)=2$, then $p(G)=1$. We also characterize the graph $G$ with $p(G)=n–2$.