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 𝐍𝐀𝐑𝐂 with the number of vertices of the smallest and largest connected component (i.e., 𝐌𝐈𝐍_𝐍𝐂𝐂 and πŒπ€π—_𝐍𝐂𝐂).

𝐌𝐈𝐍_ππ‚π‚β‰ πŒπ€π—_𝐍𝐂𝐂⇒𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂-2+ (𝐌𝐈𝐍_𝐍𝐂𝐂=1)

πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽ:𝐌𝐈𝐍_ππ‚π‚β‰ πŒπ€π—_𝐍𝐂𝐂⇒ 𝐍𝐀𝐑𝐂β‰₯𝐌𝐈𝐍_𝐍𝐂𝐂 2 +πŒπ€π—_𝐍𝐂𝐂 2

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 𝐌𝐈𝐍_𝐍𝐂𝐂 2 +πŒπ€π—_𝐍𝐂𝐂 2 is greater than or equal to 𝐌𝐈𝐍_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂-2+(𝐌𝐈𝐍_𝐍𝐂𝐂=1)), 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 𝐍𝐀𝐑𝐂 to the number of vertices 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 according to the arc generator (see FigureΒ 2.3.4) used for generating the initial digraph:




𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(≀):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰₯):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(<):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(>):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ):𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 -𝐍𝐕𝐄𝐑𝐓𝐄𝐗