### 4.3.2. Format of an invariant

As we previously saw, we have graph invariants that hold for any digraph as well as tighter graph invariants for specific graph classes. As a consequence, we partition the database in groups of graph invariants. A group of graph invariants corresponds to several invariants such that all invariants relate the same subset of graph parameters and such that all invariants are variations of the first invariant of the group taking into accounts the graph class. Therefore, the first invariant of a group has no precondition, while all other invariants have a non-empty precondition that characterises the graph class for which they hold.

EXAMPLE: As a first example consider the group of invariants denoted by Proposition 68, which relate the number of arcs $\mathrm{𝐍𝐀𝐑𝐂}$ with the number of vertices of the smallest and largest connected component (i.e., $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}$ and $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}$).

$\begin{array}{cc}& \mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\ne \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}⇒\mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}+\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}-2+\hfill \\ & \left(\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}=1\right)\hfill \end{array}$

$\begin{array}{cc}& \mathrm{𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎}:\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}\ne \mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}⇒\hfill \\ & \mathrm{𝐍𝐀𝐑𝐂}\ge \mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}^{2}+\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}^{2}\hfill \end{array}$

On the one hand, since the first rule has no precondition it corresponds to a general graph invariant. On the other hand the second rule specifies a tighter condition (since $\mathrm{𝐌𝐈𝐍}_{\mathrm{𝐍𝐂𝐂}}^{2}+\mathrm{𝐌𝐀𝐗}_{\mathrm{𝐍𝐂𝐂}}^{2}$ is greater than or equal to $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}+\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐂𝐂}-2+\left(\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐂𝐂}=1\right)\right)$, which only holds for a final graph that is reflexive, symmetric and transitive.

EXAMPLE: As a second example, consider the following group of invariants corresponding to Proposition 51, which relate the number of arcs $\mathrm{𝐍𝐀𝐑𝐂}$ to the number of vertices $\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$ according to the arc generator (see Figure 2.3.4) used for generating the initial digraph:

$\mathrm{𝐍𝐀𝐑𝐂}\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}^{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐼𝑅𝐶𝑈𝐼𝑇}:\mathrm{𝐍𝐀𝐑𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐻𝐴𝐼𝑁}:\mathrm{𝐍𝐀𝐑𝐂}\le 2·\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-2$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(\le \right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}+1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(\ge \right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}+1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(<\right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(>\right):\mathrm{𝐍𝐀𝐑𝐂}\le \frac{\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}·\left(\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1\right)}{2}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}\left(\ne \right):\mathrm{𝐍𝐀𝐑𝐂}\le {\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}^{2}-\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝐶𝑌𝐶𝐿𝐸}:\mathrm{𝐍𝐀𝐑𝐂}\le 2·\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$

$\mathrm{𝐚𝐫𝐜}_\mathrm{𝐠𝐞𝐧}=\mathrm{𝑃𝐴𝑇𝐻}:\mathrm{𝐍𝐀𝐑𝐂}\le \mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}-1$