The largest multiplicity of a distance Laplacian eigenvalue in a connected graph. The distance Laplacian of a graph is the (symmetric) matrix with row and column sums $0$, which has the negative distances between two vertices as its off-diagonal entries. This statistic is the largest multiplicity of an eigenvalue. For example, the cycle on four vertices has distance Laplacian $$ \left(\begin{array}{rrrr} 4 & -1 & -2 & -1 \\ -1 & 4 & -1 & -2 \\ -2 & -1 & 4 & -1 \\ -1 & -2 & -1 & 4 \end{array}\right). $$ Its eigenvalues are $0,4,4,6$, so the statistic is $2$. The path on four vertices has eigenvalues $0, 4.7\dots, 6, 9.2\dots$ and therefore statistic $1$.

The number of Hamiltonian cycles in a graph. A Hamiltonian cycle in a graph $G$ is a subgraph (this is, a subset of the edges) that is a cycle which contains every vertex of $G$. Since it is unclear whether the graph on one vertex is Hamiltonian, the statistic is undefined for this graph.

The monochromatic index of a connected graph. This is the maximal number of colours such that there is a colouring of the edges where any two vertices can be joined by a monochromatic path. For example, a circle graph other than the triangle can be coloured with at most two colours: one edge blue, all the others red.

The girth of a graph, which is not a tree. This is the length of the shortest cycle in the graph.

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.