### 4.3.1. Graph classes

By definition, a graph invariant has to hold for any digraph. For instance, we have the graph invariant $\mathrm{\pi \pi \pi \pi }\beta €{\mathrm{\pi \pi \pi \pi \pi \pi \pi }}^{2}$, which relates the number of arcs and the number of vertices of any digraph. This invariant is sharp since the equality is reached for a clique. However, by considering the structure of a digraph, we can get sharper invariants. For instance, if our digraph is a subset of an elementary path (e.g.,Β we use the $\mathrm{\pi \pi ΄\pi \pi »}$ arc generator depicted by FigureΒ 2.2.4) we have that $\mathrm{\pi \pi \pi \pi }\beta €\mathrm{\pi \pi \pi \pi \pi \pi \pi }-1$, which is a tighter bound of the maximum number of arcs since $\mathrm{\pi \pi \pi \pi \pi \pi \pi }-1<{\mathrm{\pi \pi \pi \pi \pi \pi \pi }}^{2}$. For this reason, we consider recurring graph classes that show up for different global constraints of the catalogue. Beside the graph classes that were introduced in SectionΒ 2.2.2.4.3 we also have the following classes relating several graph constraints:

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$: constraint defined by two graph constraints having the same initial graph, where each arc of the initial graph belongs to one of the final graph (but not to both).

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$: constraint defined by two graph constraints having the same initial graph, where each vertex of the initial graph belongs to one of the final graph (but not to both).

In addition, we also consider graph constraints such that their final graphs is a subset of the graph generated by the arc generators:

where $\mathrm{\pi ²\pi \pi \pi \pi \pi \pi \pi \pi \pi }$ is one of the following comparison operators $\beta €$, $\beta ₯$, $<$, $>$, $=$, .