4.3.1. Graph classes

By definition, a graph invariant has to hold for any digraph. For instance, we have the graph invariant 𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 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 𝑃𝐴𝑇𝐻 arc generator depicted by FigureΒ 2.2.4) we have that 𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1, which is a tighter bound of the maximum number of arcs since 𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1<𝐍𝐕𝐄𝐑𝐓𝐄𝐗 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:

  • πšŠπš™πšŠπš›πšπš’πšπš’πš˜πš—: 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).

  • πšŸπš™πšŠπš›πšπš’πšπš’πš˜πš—: 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 π™²πš˜πš–πš™πšŠπš›πš’πšœπš˜πš— is one of the following comparison operators ≀, β‰₯, <, >, =, β‰ .