The cycle graph

Kernel orbits

Data type

Crisp symmetric simple digraphs

Problematics

Maximum independent set (MIS), MIS enumeration, unlabelled kernel number.

Description

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].

Files

References

  1. R. Bisdorff and J.L. Marichal (2008). Counting non-isomorphic maximal independent sets of the n-cycle graph. Journal of Integer Sequences, Vol. 11 Article 08.5.7 (open access).
  2. The Perrin sequence A001608, Encyclopedia of Integer Sequences.
  3. Number of cyclic and palindromic compositions of n in which each term is either 2 or 3 (sequence A127682), Encyclopedia of Integer Sequences.
  4. R. Bisdorff, St-Niclas graphs, Communication, 4th Workshop on Classification, Luxembourg, December 2005

Digraph3 Data Sets

All Digraph3 data sets.