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 \(\epsilon(G)\). In this paper, we prove \(\epsilon(G) \geq p(G)\) for any graph \(G\). Especially, if \(\epsilon(G) = 2\), then \(p(G) = 1\). We also characterize the graph \(G\) with \(p(G) = n – 2\).