We consider finite simple graphs in this paper. Undefined concepts and notations will follow [1], and so we write $ G = (V(G), E(G)) $ to denote a simple graph with vertex set $ V(G) $ and edge set $ E(G) $. As in [1], for a vertex subset $ U\subseteq V(G) $, $ G[U] $ is the subgraph of $ G $ induced by $ U $. For a vertex $ u \in V(G) $, define $ N_{G}(u) = \{v\in V(G)\mid v $ is adjacent to $ u $ in $ G\} $ to be the neighborhood of vertex $ u $ in $ G $, and $ d_{G}(u) = |N_{G}(u)| $ as the degree of $ u $ in $ G $. For integers $ n, n_1, \cdots, n_t > 0 $, $ K_{n}, C_{n} $ and $ K_{n_{1}, n_{2}, \cdots, n_{t}} $ denote the complete graph on $ n $ vertices, the $ n $-cycle and the complete multipartite graph, respectively. If $ G $ and $ H $ are two vertex disjoint graphs, then $ G \cup H $ denotes the disjoint union of $ G $ and $ H $.

Throughout this paper, the vertices of a graph $ G $ are often labeled as $ V(G) = \{v_{1}, v_{2}, \cdots, v_{n}\} $ where $ n = |V(G)| $. As in [1], the adjacency matrix of $ G $ is an $ n \times n $ matrix $ A(G) = (a_{ij})_{n\times n} $, where $ a_{ij} $ is the number of edges joining $ v_{i} $and $ v_{j} $in $ G $. The eigenvalues $ \lambda_{1}, \lambda_{2}, \lambda_{3}, \cdots, \lambda_{n} $ of $ A(G) $ are said to be the eigenvalues of the graph $ G $ and to form the spectrum of this graph. The number of positive, negative and zero eigenvalues in the spectrum of $ G $ are called positive inertia index, negative inertia index and nullity of the graph $ G $, and are denoted by $ p(G) $, $ n(G) $ and $ \eta(G) $, respectively. Obviously $ p(G)+n(G)+\eta(G) = n $. The rank of $ G $, written as $ r(G) $, is the number of nonzero eigenvalues in the spectrum of $ G $. It follows from the definitions that $ r(G) = p(G)+n(G) = n-\eta(G) $.

In chemistry, a conjugated hydrocarbon molecule can be modeled by its molecular graph $ G $, where the vertices of $ G $ represent the carbon atoms, and the edges of $ G $ represent the carbon-carbon bonds of the conjugated molecule. The nullity (as well as the rank) of a molecular graph $ G $ has a number of important applications in chemistry. For example, it is known [2] that $ \eta(G) = 0 $ is a necessary condition for the molecule represented by $ G $ to be chemically stable. More studies on nullity or rank of graphs can be found in [3-28], among others. To the best of our knowledge, very few studies on the positive and negative inertia indices of graphs were conducted. In [29], Hoffman showed that a graph has exactly one negative eigenvalue if and only if its non-isolated vertices form a complete bipartite graph. In [30], Smith showed that a graph has exactly one positive eigenvalue if and only if its non-isolated vertices form a complete multipartite graph. In [31], graph $ G $ is characterized with $ p(G)\geq n-2 $, where $ n = |V(G)| $. It raises the problem of characterizing graph $ G $ with small negative inertia indices.

This motivates the current research. In this paper, we present a complete characterization for graphs $ G $ with $ n(G)\leq 2 $, and for graphs $ G $ with both $ \delta(G) = 1 $ and $ n(G)\leq 3 $, where $ \delta(G) $ is the smallest degree of $ G $.

This paper is organized as follows: in Section 2, preliminary lemmas will be presented. A Characterization for graph $ G $ with $ n(G)\leq 2 $, and for graph $ G $ with pendent vertices and with $ n(G)\leq 3 $ are given in Sections 3 and 4. The characterization of graph $ G $ with $ n(G)\leq 2 $ extends the former result of Hoffman in [29].

Lemma 2.1   Let $ G $ and $ H $ be graphs. Then

$ p(G\cup H) = p(G)+p(H); \ \ n(G\cup H) = n(G)+n(H). $

Lemma 2.2   (see [30]) A graph $ G $ has exactly one positive eigenvalue if and only if its non-isolated vertices form a complete multipartite graph.

Lemma 2.3   (see [9, 32]) (the Cauchy inequalities) Let $ A $ be Hermtian matrix with eigenvalues $ \lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n} $, $ B $ be one of its principal submatrices and $ B $ have eigenvalues $ \mu_{1}\geq \cdots \geq \mu_{m} $. Then the inequalities $ \lambda_{n-m+i} \leq \mu_{i} \leq \lambda_{i}(i = 1, \cdots, m) $ hold.

Lemma 2.4   Let $ H $ be a vertex-induced subgraph of $ G $. Then

(1) $ r(H)\leq r(G), \ \ p(H)\leq p(G) $ and $ n(H)\leq n(G). $

(2) If $ r(H) = r(G) $, then $ p(H) = p(G) $ and $ n(H) = n(G). $

Proof   Lemma 2.4 follows from Lemma 2.3 and from the inequality $ r(H) = p(H)+n(H)\leq p(G)+n(G) = r(G) $.

Lemma 2.5   (see [33]) Let $ G $ be a connected graph with rank $ k \ (\geq 2) $. Then there exists a vertex-induced subgraph $ H $ (of $ G $) on $ k $ vertices such that $ r(H) = k $.

As in [1], a vertex subset $ I \subseteq V(G) $ of a graph $ G $ is an independent set (also referred as a stable set) of $ G $ if $ G[I] $, the subgraph induced by $ I $, is edgeless. Let $ m = (m_{1}, m_{2}, . . . , m_{n}) $ be a vector of positive integers. Denote by $ G \circ m $ the graph obtained from $ G $ by replacing each vertex $ v_{i} $ of $ G $ with an independent set of $ m_{i} $ vertices $ v^{1}_{i}, v^{2}_{i}, \cdots, v^{m_{i}}_{i} $ and joining $ v^{s}_{i} $ with $ v^{t}_{j} $ if and only if $ v_{i} $ and $ v_{j} $ are adjacent in $ G $ $ (1\leq s\leq m_{i}, \ 1\leq t\leq m_{j}) $. The resulting graph $ G\circ m $ is said to be obtained from $ G $ by multiplication of vertices.

Let $ \Omega $ be the set of some graphs, we denote by $ {\mathcal{M}}(\Omega) $ the class of all graphs that can be constructed from one of the graphs in $ \Omega $ by multiplication of vertices.

Lemma 2.6   (see [5, 6]) Let $ G $ and $ H $ be graphs. If $ G\in {\mathcal{M}}(\{H\}) $, then $ r(G) = r(H) $. Furthermore, in this case, we have both $ p(G) = p(H) $ and $ n(G) = n(H) $.

A graph is called a basic graph if it has no isolated vertex and can not be obtained from other graphs by multiplication of vertices. By definition, a graph with no isolated vertices is not a basic graph if and only if it has two vertices which have same neighborhoods. By Lemma 2.6, it suffices to study basic graphs when we investigate graph invariants such as the rank, the positive inertia index and the negative inertia index.

Lemma 2.7   (see [19]) Let $ G $ be a graph containing a pendant vertex, and let $ H $ be the induced subgraph of $ G $ obtained by deleting the pendant vertex together with the vertex adjacent to it. Then $ p(G) = p(H)+1 $ and $ n(G) = n(H)+1 $.

Lemma 2.8   (see [5, 6, 8]) Let $ G $ be a connected graph. Then

(a) $ r(G) = 2 $ if and only if $ G \in {\mathcal{M}}(\{K_{2}\}) $,

(b) $ r(G) = 3 $ if and only if $ G\in {\mathcal{M}}(\{K_{3}\}) $,

(c) $ r(G) = 4 $ if and only if $ G\in {\mathcal{M}}(\Omega_{1}) $, where $ \Omega_{1} = \{H_{1}, H_{2}, \cdots, H_{8}\} $,

(d) $ r(G) = 5 $ if and only if $ G\in {\mathcal{M}}(\Omega_{2}) $, where $ \Omega_{2} = \{G_{1}, G_{2}, \cdots, G_{24}\} $,

where graphs $ H_{i}\; (i = 1, 2, \cdots, 8) $ are depicted in Figure 1 and graphs $ G_{i}\; (i = 1, 2, \cdots, 24) $ are depicted in Figure 2.

Lemma 2.9   (see [31]) Let $ G $ be a graph of order $ n $, then $ p(G) = n-2 $ if and only if one of the following holds

(1) $ n = 2 $, $ G\cong 2K_{1} $; or

(2) $ n = 3 $, $ G\cong K_{1}\bigcup K_{2} $, $ K_{1, 2} $ or $ K_{3} $; or

(3) $ n = 4 $, $ G\cong F_{1}, F_{2} $ or $ F_{3} $; or

(4) $ n = 5 $, $ G\cong C_{5} $,

where graphs $ F_{i}(i = 1, 2, 3) $ are depicted in Figure 3.

The following lemmas will be needed in our characterization.

Lemma 3.1   (see [29]) A graph has exactly one negative eigenvalue if and only if its non-isolated vertices form a complete bipartite graph. In other words, if $ G $ is a connected graph, then $ n(G) = 1 $ if and only if $ G\in {\mathcal{M}}(\{K_{2}\}) $.

Lemma 3.2   Let $ G $ be a connected graph. Then $ n(G) = 2 $ if and only if $ G\in{\mathcal{M}}(\Omega_{3}) $, where $ \Omega_{3} = \{K_{3}, C_{5}, H_{1}, H_{2}, $ $ \cdots, H_{7}\}, $ and the graphs $ H_{i} $ $ (i = 1, 2, \cdots, 7) $ are defined in Figure 1.

Proof   It is routine to verify that $ n(G) = 2 $ for $ G \in \{K_{3}, C_{5}\} \cup \{H_{i} | 1 \le i \le 7\} $. Thus the sufficiency follows from Lemma 2.6.

To prove the necessity, we note that $ r(G)>n(G) = 2 $. If $ r(G) = 3, $ then by Lemma 2.8 (b), $ G\in {\mathcal{M}}(\{K_{3}\}) $. If $ r(G) = 4, $ then by Lemma 2.8 (c), $ G\in {\mathcal{M}}(\{H_{1}, H_{2}, \cdots, H_{8}\}) $. However, as direct computation yields $ n(H_{8}) = 3 $, we must have $ G\in {\mathcal{M}}(\{H_{1}, H_{2}, \cdots, H_{7}\}) $.

If $ r(G) = 5 $, then by Lemma 2.8 (d), $ G\in {\mathcal{M}}(\{G_{1}, G_{2}, \cdots, G_{24}\}) $. Direct computation yields $ n(G_{2}) = 4 $. To determine the values of the other $ n(G_i) $'s, we utilize Table 1 of [9] to find $ n(G_{i}) = 3 $, $ 3 \le i \le 8 $. By deleting the vertices which be marked $ \ast $ in graphs depicted in Figure 2, we observe that each $ G_{i} $, $ 9 \le i \le 18 $, has a vertex-induced subgraph isomorphic to $ G_{4} $, that each of $ G_{19}, G_{20} $ and $ G_{21} $ has a vertex-induced subgraph isomorphic to $ G_{5} $, that each of $ G_{22} $ and $ G_{23} $ has a vertex-induced subgraph isomorphic to $ G_{6} $, and that $ G_{24} $ has a vertex-induced subgraph isomorphic to $ G_{7} $. It follows by Lemma 2.4 (2) that $ n(G_{i}) = 3 $, $ 9 \le i \le 24 $. Hence in this case, $ G\in {\mathcal{M}}(\{G_{1}\}) = {\mathcal{M}}(\{C_{5}\}) $.

If $ r(G) = k\geq 6 $, then by Lemma 2.5, there exists a vertex-induced subgraph $ H $ (of $ G $) on $ k $ vertices such that $ r(H) = k $. Furthermore, by Lemma 2.4(2), we have $ n(H) = 2 $ and $ p(H) = k-2 $. However, there does not exist such a graph $ H $ by Lemma 2.9. This means that there does not exist graph $ G $ with $ r(G) = k\geq 6 $ and $ n(G) = 2 $.

A graph $ G $ is called basic extremal graph with respect to $ n(G) = 2 $, if $ G $ is a basic graph with $ n(G) = 2 $, and $ G $ is not a proper vertex-induced subgraph of any other basic graphs $ H $ with $ n(H) = 2 $. By definition, since $ K_{3} $ is a proper vertex-induced subgraph of $ H_{6} $, hence $ K_{3} $ is not a basic extremal graph with respect to $ n(G) = 2 $, the same graphs $ H_{i}\; (i = 1, 2, 3, 4, 5) $ are not basic extremal graph with respect to $ n(G) = 2 $. However, it is routine to verify that the graphs $ G $ in Figure 4 are basic extremal graphs with respect to $ n(G) = 2 $.

Theorem 3.1 now follows from Lemma 3.1 and Lemma 3.2.

Theorem 3.1   Let $ G $ be a graph. Then $ n(G)\leq 2 $ if and only if $ G\in{\mathcal{M}}(\Omega_{4}) $, where $ \Omega_{4} $ is the set of all vertex-induced subgraph of each graph in $ \Theta_{1} = \{C_{5}\cup K_{1}, H_{6}\cup K_{1}, H_{7}\cup K_{1}\} $, and $ C_{5}, H_{6}, H_{7} $ are depicted in Figure 4.

Let $ H $ be a graph with $ V(H) = \{v_{1}, v_{2}, \cdots, v_{n}\} $ and $ m = (m_{1}, m_{2}, . . . , m_{n}) $ be a vector with $ m_{i} = 1 $ or $ 2 $, $ (i = 1, 2, \cdots, n) $. Then $ V(H) $ can be divided into two sets: $ V_{1} = \{v_{i}\in V(H)\mid m_{i} = 1\} $ and $ V_{2} = \{v_{i}\in V(H)\mid m_{i} = 2\} $. Let $ v^{1}_{i} $ and $ v^{2}_{i} $ be the vertices in $ H\circ m $ by multiplying the vertex $ v_{i} $ in $ H $ when $ m_{i} = 2 $. For a subset $ U\subseteq V_{1} $, we construct a graph $ (H\circ m)^{U} $ as follows

$ \begin{eqnarray*} V((H\circ m)^{U}) & = & \{x, y\}\cup V(H\circ m), \\ E((H\circ m)^{U}) & = & \{(x, y)\}\cup \{(y, v^{1}_{i})|\forall m_{i} = 2\}\cup\{(y, v_{i})|v_{i}\in U\}\cup E(H\circ m). \end{eqnarray*} $

By the definition, $ (H\circ m)^{U} $ has a pendent vertex $ x $.

Lemma 4.1   If $ H $ is a basic graph, then $ (H\circ m)^{U} $ is also a basic graph.

Proof   For any $ i, j\in \{1, 2, \cdots, n\} $, if $ i\not = j $, as $ H $ is a basic graph, then $ N_{H}(v_{i})\not = N_{H}(v_{j}) $. So $ N_{(H\circ m)^{U}}(v^{s}_{i})\not = N_{(H\circ m)^{U}}(v^{t}_{j}) $ ($ 1\leq s\leq m_{i} $, $ 1\leq t\leq m_{j} $). If $ i = j $ and $ m_{i} = 2 $, by the construction of the graph $ (H\circ m)^{U} $, we have $ y\in N_{(H\circ m)^{U}}(v^{1}_{i}) $ and $ y\notin N_{(H\circ m)^{U}}(v^{2}_{i}) $; $ x\in N_{(H\circ m)^{U}}(y) $ and $ x\notin N_{(H\circ m)^{U}}(v) $ for all $ v(\neq y)\in V((H\circ m)^{U}) $; $ N_{(H\circ m)^{U}}(x) = \{y\} $ and $ N_{(H\circ m)^{U}}(v)\not = \{y\} $ for all $ v(\neq x)\in V((H\circ m)^{U}) $ (this is because $ H $ has no isolated vertex). In a word, any two vertices in $ (H\circ m)^{U} $ don't have the same neighborhoods. Therefore, $ (H\circ m)^{U} $ is a basic graph. This proves the lemma.

Let $ \Gamma(H) = \{((H\circ m)^{U}|U\in V_{1}, m = (m_{1}, m_{2}, \cdots, m_{n}), m_{i} = 1\ \ \text {or} \ \ 2\} $ be the collection of all graphs $ (H\circ m)^{U} $. For the convenience of drawing, when $ m_{i} = 2 $, we use a hollow circle to indicate two vertices $ v^{1}_{i} $ and $ v^{2}_{i} $, which have the same neighborhoods in $ H\circ m $, the vertex $ y $ is adjacent to $ v^{1}_{i} $ and not adjacent to $ v^{2}_{i} $, and we use a black dot to indicate exactly one vertex. For example, the graph $ (H\circ m)^{U} $ is depicted in Figure 6, where $ H = C_{5} $, $ V(H) = \{v_{1}, v_{2}, v_{3}, v_{4}, v_{5}\} $, $ m = (2, 2, 1, 1, 1) $ and $ U = \{v_{3}, v_{4}\} $.

Lemma 4.2   Let $ G $ be a connected graph with pendent vertices and $ n(G) = 3 $. Then $ G\in {\mathcal {M}}(\Omega_{5}) $, where $ \Omega_{5} = \Gamma(2K_{2})\cup\Gamma(K_{3})\cup\Gamma(C_{5})\cup\bigcup_{i = 1}^{7}\Gamma(H_{i}) $ and $ H_{i}\ (i = 1, 2, \cdots, 7) $ are depicted in Figure 1.

Proof   Without loss of generality, assume that $ G $ is a basic graph. Let $ H $ be the induced subgraph of $ G $ obtained by deleting the pendant vertex $ x $ together with the vertex $ y $ adjacent to it. By Lemma 2.7, we have $ n(H) = 2 $. Furthermore, $ H $ does not have isolated vertices (if not, then the $ G $ contains at least an isolated vertex or two pendant vertices all adjacent to $ y $, so $ G $ is not a connected graph, or $ G $ is not a basic graph, a contradiction). If the graph $ H $ is not connected, then by Lemma 3.1, $ H\in M(\{2K_{2}\}) $. If the graph $ H $ is connected, then by Lemma 3.2, $ H\in {\mathcal {M}}(\{K_{3}, C_{5}, H_{1}, H_{2}, \cdots, H_{7}\}) $, where graphs $ H_{i} $ $ (i = 1, 2, \cdots, 7) $ are depicted in Figure 1. We present the proof for the case when $ H = K_{3}\circ m $, where $ m = (m_{1}, m_{2}, \cdots, m_{n}) $ be a vector of positive integers, as the proofs for other cases are similar and will be omitted. If $ m_{i}\geq 3 $, then there exist $ s, t\in\{1, 2, \cdots, m_{i}\} $ such that $ N_{G}(v^{s}_{i}) = N_{G}(v^{t}_{i}) $. If $ m_{i} = 2 $, $ v^{1}_{i} $ and $ v^{2}_{i} $ are all adjacent to $ y $ or none is adjacent to $ y $, then $ N_{G}(v^{1}_{i}) = N_{G}(v^{2}_{i}) $. However, $ G $ is a basic graph, this is a contradiction. So $ m_{i}\leq 2 $, furthermore, one and only one of the two vertices $ v^{1}_{i} $ and $ v^{2}_{i} $ is adjacent to $ y $ when $ m_{i} = 2 $. Therefore, we conclude that $ G\in \Gamma(2K_{2})\cup\Gamma(K_{3})\cup\Gamma(C_{5})\cup\bigcup_{i = 1}^{7}\Gamma(H_{i}). $

For vectors $ m_{1} = (2, 2, 2, 2, 2) $ and $ m_{2} = (2, 2, 2, 2, 2, 2) $, define $ P_{1} = (C_{5}\circ m_{1})^{\emptyset} $, $ P_{2} = (H_{6}\circ m_{2})^{\emptyset} $, $ P_{3} = (H_{7}\circ m_{2})^{\emptyset} $, as depicted in Figure 6. If

$ G\in \Gamma(2K_{2})\cup\Gamma(K_{3})\cup\Gamma(C_{5})\cup\cup_{i = 1}^{7}\Gamma(H_{i}), $

it is straightforward to verity that graphs $ G $ are a vertex-induced subgraph of $ P_{1} $, $ P_{2} $, or $ P_{3} $. Hence Theorem 4.1 below follows from Lemma 4.2.

Theorem 4.1   Let $ G $ be a graph with pendent vertices and $ n(G)\leq 3 $. Then $ G\in {\mathcal {M}}(\Omega_{6}) $, where $ \Omega_{6} $ is the set of all vertex-induced subgraph of each graph in $ \Theta_{2} = \{P_1\cup K_{1}, P_2\cup K_{1}, P_3\cup K_{1}\} $, where $ P_{i}\; (i = 1, 2, 3) $ are depicted in Figure 6.