The dimension of a graph. The dimension of a graph is the least integer $n$ such that there exists a representation of the graph in the Euclidean space of dimension $n$ with all vertices distinct and all edges having unit length. Edges are allowed to intersect, however.

The bandwidth of a graph. The bandwidth of a graph is the smallest number $k$ such that the vertices of the graph can be ordered as $v_1,\dots,v_n$ with $k \cdot d(v_i,v_j) \geq |i-j|$. We adopt the convention that the singleton graph has bandwidth $0$, consistent with the bandwith of the complete graph on $n$ vertices having bandwidth $n-1$, but in contrast to any path graph on more than one vertex having bandwidth $1$. The bandwidth of a disconnected graph is the maximum of the bandwidths of the connected components.

The degeneracy of a graph. The degeneracy of a graph $G$ is the maximum of the minimum degrees of the (vertex induced) subgraphs of $G$.

The proper pathwidth of a graph. The proper pathwidth $\operatorname{ppw}(G)$ was introduced in [1] as the minimum width of a proper-path-decomposition. Barioli et al. [2] showed that if $G$ has at least one edge, then $\operatorname{ppw}(G)$ is the minimum $k$ for which $G$ is a minor of the Cartesian product $K_k \square P$ of a complete graph on $k$ vertices with a path; and further that $\operatorname{ppw}(G)$ is the minor monotone floor $\lfloor \operatorname{Z} \rfloor(G) := \min\{\operatorname{Z}(H) \mid G \preceq H\}$ of the [[St000482|zero forcing number]] $\operatorname{Z}(G)$. It can be shown [3, Corollary 9.130] that only the spanning supergraphs need to be considered for $H$ in this definition, i.e. $\lfloor \operatorname{Z} \rfloor(G) = \min\{\operatorname{Z}(H) \mid G \le H,\; V(H) = V(G)\}$. The minimum degree $\delta$, treewidth $\operatorname{tw}$, and pathwidth $\operatorname{pw}$ satisfy $$\delta \le \operatorname{tw} \le \operatorname{pw} \le \operatorname{ppw} = \lfloor \operatorname{Z} \rfloor \le \operatorname{pw} + 1.$$ Note that [4] uses a different notion of proper pathwidth, which is equal to bandwidth.

The acyclic chromatic index of a graph. An acyclic edge coloring of a graph is a proper colouring of the edges of a graph such that the union of the edges colored with any two given colours is a forest. The smallest number of colours such that such a colouring exists is the acyclic chromatic index.

The treewidth of a graph. A graph has treewidth zero if and only if it has no edges. A connected graph has treewidth at most one if and only if it is a tree. A connected graph has treewidth at most two if and only if it is a series-parallel graph.

The pathwidth of a graph.

The acyclic chromatic number of a graph. This is the smallest size of a vertex partition $\{V_1,\dots,V_k\}$ such that each $V_i$ is an independent set and for all $i,j$ the subgraph inducted by $V_i\cup V_j$ does not contain a cycle.

The Hadwiger number of the graph. Also known as clique contraction number, this is the size of the largest complete minor.

The largest eigenvalue of a graph if it is integral. If a graph is $d$-regular, then its largest eigenvalue equals $d$. One can show that the largest eigenvalue always lies between the average degree and the maximal degree. This statistic is undefined if the largest eigenvalue of the graph is not integral.