4.3.1. Graph classes

By definition, a graph invariant has to hold for any digraph. For instance, we have the graph invariant $\mathrm{𝐍𝐀𝐑𝐂}\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}^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{𝑃𝐴𝑇𝐻}$ arc generator depicted by Figure 2.3.4) we have that $\mathrm{𝐍𝐀𝐑𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1$, which is a tighter bound of the maximum number of arcs since $\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1<{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}^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.3.2.4.3 we also have the following classes relating several graph constraints:

• $\mathrm{𝚊𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$: constraint defined by two graph constraints having the same initial graph, where each arc of the initial graph belongs to one of the final graphs (but not to both).

• $\mathrm{𝚟𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$: constraint defined by two graph constraints having the same initial graph, where each vertex of the initial graph belongs to one of the final graphs (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:

• $\mathrm{𝐶𝐻𝐴𝐼𝑁}$,

• $\mathrm{𝐶𝐼𝑅𝐶𝑈𝐼𝑇}$,

• $\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$,

• $\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(\mathrm{𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗}\right)$

• $\mathrm{𝐺𝑅𝐼𝐷}$,

• $\mathrm{𝐿𝑂𝑂𝑃}$,

• $\mathrm{𝑃𝐴𝑇𝐻}$,

• $\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$,

• $\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$\left(\mathrm{𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗}\right)$,

• $\mathrm{𝑆𝑌𝑀𝑀𝐸𝑇𝑅𝐼𝐶}\_\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$,

• $\mathrm{𝑆𝑌𝑀𝑀𝐸𝑇𝑅𝐼𝐶}\_\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$\left(\mathrm{𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗}\right)$,

where $\mathrm{𝙲𝚘𝚖𝚙𝚊𝚛𝚒𝚜𝚘𝚗}$ is one of the following comparison operators $\le$, $\ge$, $<$, $>$, $=$, $\ne$.