Bounds for the positive or negative inertia index of a graph

Abstract

Let $G$ be a graph and let $A(G)$ be adjacency matrix of $G$.The positive inertia index (respectively, the negative inertia index) of $G$, denoted by $p(G)$ (respectively, $n(G)$), is defined to be the number of positive eigenvalues (respectively, negative eigenvalues) of $A(G)$. In this paper, we present the bounds for $p(G)$ and $n(G)$ as follows: $$m(G)-c(G)\le p(G)\le m(G)+c(G),m(G)-c(G)\le n(G)\le m(G)+c(G),$$ where $m(G)$ and $c(G)$ are respectively the matching number and the cyclomatic number of $G$. Furthermore, we characterize the graphs which attain the upper bounds or the lower bounds respectively.

References in corpus (1)

• The signature of line graphs and power trees

Cited by in corpus (2)

• Mixed graphs with cut vertices having exactly two positive eigenvalues
• On the inertia index of a mixed graph with the matching number