The number of connected components of a graph.

The (zero)-forcing number of a graph. This is the minimal number of vertices initially coloured black, such that eventually all vertices of the graph are coloured black when using the following rule: when $u$ is a black vertex of $G$, and exactly one neighbour $v$ of $u$ is white, then colour $v$ black.

The cop number of a graph. This is the minimal number of cops needed to catch the robber. The algorithm is from [2].

The maximal multiplicity of a Laplacian eigenvalue in a graph.

The side length of the largest staircase partition fitting into a partition. For an integer partition $(\lambda_1\geq \lambda_2\geq\dots)$ this is the largest integer $k$ such that $\lambda_i > k-i$ for $i\in\{1,\dots,k\}$. In other words, this is the length of a longest (strict) north-east chain of cells in the Ferrers diagram of the partition, using the English convention. Equivalently, this is the maximal number of non-attacking rooks that can be placed on the Ferrers diagram. This is also the maximal number of occurrences of a colour in a proper colouring of a Ferrers diagram. A colouring of a Ferrers diagram is proper if no two cells in a row or in a column have the same colour. The minimal number of colours needed is the maximum of the length and the first part of the partition, because we can restrict a latin square to the shape. We can associate to each colouring the integer partition recording how often each colour is used, see [1]. This statistic records the largest part occurring in any of these partitions.

The Euler characteristic of a graph according to Knill. This is $$\sum_{k\geq 1} (-1)^{k-1} c_k,$$ where $c_k$ is the number of cliques with $k$ vertices.

The order dimension of the partition. Given a partition $\lambda$, let $I(\lambda)$ be the principal order ideal in the Young lattice generated by $\lambda$. The order dimension of a partition is defined as the order dimension of the poset $I(\lambda)$.

The minimal number of edges to add to make a graph Hamiltonian. A graph is Hamiltonian if it contains a cycle as a subgraph, which contains all vertices.

The Euler characteristic of a graph. The '''Euler characteristic''' $\chi$ of a topological space is the alternating sum of the dimensions of the homology groups $$\chi(X) = \sum_{k \geq 0} (-1)^k \dim H_k(X).$$ For a finite simplicial complex, this is equal to the alternating sum $\sum_{k\geq 0} (-1)^k f_k$ where $f_k$ the number of $k$-dimensional simplices. A (simple) graph is a simplicial complex of dimension at most one; its vertices are the 0-simplices and its edges are the 1-simplices. For a connected graph, the Euler characteristic is equal to $1 - g$ where $g$ is the cyclomatic number.

The number of cut vertices of a graph. A cut vertex is one whose deletion increases the number of connected components.