Circulant Graphs

Description

A circulant graph C_n^{s₁ … s_k} has n vertices, numbered from 0 to n−1. For each s_i, every vertex v is adjacent to vertex v+s_i, modulo n.

Generator

The generator, david_gen_circulant.c (depends on bit.h), takes as parameters the number of vertices, n, and a list skip₁ … skip_k.

	$ david_gen_circulant n skip₁ … skip_k

For example, the graph pictured above was generated with

	$ david_gen_circulant 10 2 3

Implementation

The generation of the graph follows simply from the mathematical definition: n vertices are created, and then for each s_i, an edge is added between v and (v+s_i)%n for each vertex v.

Timing

I timed the dominating set algorithms on four circulant graphs, stored in david_hard_interesting.txt. The graphs were:

C₁₀₀^{1, 2, 3}
C₁₀₀^{3, 7, 11}
C₁₀₀^{1, 12, 37}
C₁₀₀^{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}

Each program was given 8 minutes to run.

	graph1	graph2	graph3	graph4	time
bill	15	16	18	5	17.86
lorena	15	16	n/a	n/a	480
patrick	15	16	n/a	n/a	480
paulo	15	16	26	n/a	480
carlos	15	16	26	n/a	480
david	15	n/a	n/a	n/a	480
giancarlo	15	16	18	5	5.73
di	15	16	n/a	n/a	480
wendy	15	16	26	n/a	480
thiago	15	16	18	5	5.64
manjeet	15	16	18	5	38.82