The radius of a connected graph. This is the minimum eccentricity of any vertex.

The size of a minimal vertex cover of a graph. A '''vertex cover''' of a graph $G$ is a subset $S$ of the vertices of $G$ such that each edge of $G$ contains at least one vertex of $S$. Finding a minimal vertex cover is an NP-hard optimization problem.

The matching number of a graph. For a graph $G$, this is defined as the maximal size of a '''matching''' or '''independent edge set''' (a set of edges without common vertices) contained in $G$.

The number of positive eigenvalues of the adjacency matrix of the graph.

The length of a longest pair of twins in a permutation. A pair of twins in a permutation is a pair of two disjoint subsequences which are order isomorphic.

The maximal size of a pair of weak twins for a permutation. A pair of weak twins in a permutation is a pair of two disjoint subsequences of the same length with the same descent pattern. More formally, a pair of weak twins of size $k$ for a permutation $\pi$ of length $n$ are two disjoint lists $1 \leq i_1 < \dots < i_k \leq n$ and $1 \leq j_1 < \dots < j_k \leq n$ such that $\pi(i_a) < \pi(i_{a+1})$ if and only if $\pi(j_a) < \pi(j_{a+1})$ for all $1 \leq a < k$.

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$.

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 achromatic number of a graph. This is the maximal number of colours of a proper colouring, such that for any pair of colours there are two adjacent vertices with these colours.