The second largest eigenvalue of a graph if it is integral. This statistic is undefined if the second largest eigenvalue of the graph is not integral. Chapter 4 of [1] provides lots of context.

The number of prime nodes in the modular decomposition of a graph.

The number of different graphs obtained from the given graph by removing an edge.

The degree of the minimal polynomial of the largest Laplacian eigenvalue of a graph.

The Grundy number of a graph. The Grundy number $\Gamma(G)$ is defined to be the largest $k$ such that $G$ admits a greedy $k$-coloring. Any order of the vertices of $G$ induces a greedy coloring by assigning to the $i$-th vertex in this order the smallest positive integer such that the partial coloring remains a proper coloring. In particular, we have that $\chi(G) \leq \Gamma(G) \leq \Delta(G) + 1$, where $\chi(G)$ is the chromatic number of $G$ ([[St000098]]), and where $\Delta(G)$ is the maximal degree of a vertex of $G$ ([[St000171]]).

The game chromatic number of a graph. Two players, Alice and Bob, take turns colouring properly any uncolored vertex of the graph. Alice begins. If it is not possible for either player to colour a vertex, then Bob wins. If the graph is completely colored, Alice wins. The game chromatic number is the smallest number of colours such that Alice has a winning strategy.

The tree-depth of a graph. The tree-depth $\operatorname{td}(G)$ of a graph $G$ whose connected components are $G_1,\ldots,G_p$ is recursively defined as $$\operatorname{td}(G)=\begin{cases} 1, & \text{if }|G|=1\\ 1 + \min_{v\in V} \operatorname{td}(G-v), & \text{if } p=1 \text{ and } |G| > 1\\ \max_{i=1}^p \operatorname{td}(G_i), & \text{otherwise} \end{cases}$$ Nešetřil and Ossona de Mendez [2] proved that the tree-depth of a connected graph is equal to its minimum elimination tree height and its centered chromatic number (fewest colors needed for a vertex coloring where every connected induced subgraph has a color that appears exactly once). Tree-depth is strictly greater than [[St000536|pathwidth]]. A [[St001120|longest path]] in $G$ has at least $\operatorname{td}(G)$ vertices [3].

The minimal number of edges to add or remove to make a graph edge transitive. A graph is edge transitive, if for any two edges, there is an automorphism that maps one edge to the other.

The minimal number of edges to add or remove to make a graph a cograph. A cograph is a graph that can be obtained from the one vertex graph by complementation and disjoint union.

The biclique partition number of a graph. The biclique partition number of a graph is the minimum number of pairwise edge disjoint complete bipartite subgraphs so that each edge belongs to exactly one of them. A theorem of Graham and Pollak [1] asserts that the complete graph $K_n$ has biclique partition number $n - 1$.