Crisp symmetric simple digraphs
Maximum independent set (MIS), MIS enumeration, unlabelled kernel number.
Cycle graphs of order n are the simplest circulant digraphs {Z_n, [1,-1]}. They consists of a single Hamiltonian cycle of length n. Being symmetric, the kernels in Cn arge given by the set of maximal independent sets (MIS), denoted MIS(n). The number of MIS in Cn, denoted #MIS(n), is determined by the Perrin sequence. (A001608).
The cycle graph Cn admits the dihedral automorphism group, which partitions the set MIS(n) into a set of isomorphic MIS orbits, denoted Ot(n), where 0 <= t <= n/2 denotes the type of symmetry of the orbit, of cardinalities denoted #Ot(n). The MIS in Ot admits t central symmetry axes reducing the size of the orbit proportionnally. Thus. the size of Ot is 2*n for t= 0, and Floor(n/t) otherwise. In general:
(1) #MIS(n) = 2*n * #O0(n) + n * #O1(n) + n/2 * #O2(n) + ... + 2 * #On/2(n).
C5, the Andrasfai graph of order 2 for instance, admits 5 MISs, all of which are isomorphic under its automorphism group, such that #O1(5) = 5. The table below shows the figures for cycle graphs Cn up to n = 20. For n = 50, the Perrin sequence announces #MIS(50) = 1 276 942, with #O(50)= 13 190, of which #O0(50) = 12 359, #O1(50) = 813, #O2(50) = 15, #O5(50) = 1 and #O25(50) = 1.
n | #MIS(n) | #O(n) | #O0(n) | #O1(n) | #O2(n) | #O3(n) | #O4(n) | #O5(n) | #O6(n) | #O7(n) | #O8(n) | #O9(n) | #O10(n) | ... | #O15(n) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | 2 | 1 | 1 | ||||||||||||
3 | 3 | 1 | 1 | ||||||||||||
4 | 2 | 1 | 1 | ||||||||||||
5 | 5 | 1 | 1 | ||||||||||||
6 | 5 | 2 | 1 | 1 | |||||||||||
7 | 7 | 1 | 1 | ||||||||||||
8 | 10 | 2 | 1 | 1 | |||||||||||
9 | 12 | 2 | 1 | 1 | |||||||||||
10 | 17 | 3 | 1 | 1 | 1 | ||||||||||
11 | 22 | 2 | 2 | ||||||||||||
12 | 29 | 4 | 2 | 1 | 1 | ||||||||||
13 | 39 | 3 | 3 | ||||||||||||
14 | 51 | 5 | 3 | 1 | 1 | ||||||||||
15 | 68 | 5 | 1 | 2 | 1 | 1 | |||||||||
16 | 90 | 7 | 5 | 1 | 1 | ||||||||||
17 | 119 | 6 | 1 | 5 | |||||||||||
18 | 158 | 10 | 1 | 6 | 1 | 1 | 1 | ||||||||
19 | 209 | 9 | 2 | 7 | |||||||||||
20 | 277 | 14 | 2 | 9 | 1 | 1 | 1 | ||||||||
... | ... | ... | ... | ... | ... | ||||||||||
30 | 4610 | 104 | 54 | 44 | 2 | 1 | 1 | 1 | ... | 1 |
From the fact that #MIS(n) follows a Perrin sequence, we may deduce that :
(2) #MIS(n) = #MIS(n-2) + #MIS(n-3)
Asymptotically, #MIS(n) ~ r^n, with r=1.3247179572447... the inverse of the real root of 1-x^2-x^3=0 (see A001608). If n>9 then #MIS(n)=round(r^n) (Ralf Stephan (ralf(AT)ark.in-berlin.de), 2002).
To prove equation (2), it is possible to show a coordinated unique extension of each MIS in MIS(n-2) and each MIS in MIS(n-3) which determines precisely the set MIS(n). This demonstration by the way defines a particularly efficient recursive algorithm for enumerating all MIS in Cn, we have implemented in C.
Furthermore, from the orbit enumeration, we discover three apparently unknown integer sequences: The total number of orbits #O(n), the type 0 orbits #O0(n), and the type 1 orbits #O1(n) [see 1,3].