Characterizations of graphs with given inertia index achieving the maximum diameter

ABSTRACT

The positive (resp., negative) inertia index of a graph G, denoted by $p\left(G\right)$ (resp., $n\left(G\right)$), is defined to be the number of positive (resp., negative) eigenvalues of its adjacency matrix. A simple result shows that $1\le d\left(G\right)\le 2p\left(G\right)$ and $1\le d\left(G\right)\le 2n\left(G\right)$, where $d\left(G\right)$ is the diameter of G. In this paper we determine the sufficient and necessary conditions when each of the equalities holds.

KEYWORDS:

• Positive inertia index
• negative inertia index
• diameter

AMS CLASSIFICATION:

• 05C50

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Supported by National Natural Science Foundation of China (11701008), Anhui Provincial Natural Science Foundation (1808085QA04) and Educational Commission of Anhui Province of China (KJ2018A0081).