I was going through some families of graph and got introduced to circulant graphs. Got the following link of circulant graphs, but I am unable to get it. What do they mean by the list. Kindly help me in clearing my doubt. Thanks for taking out time.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ They mean that, for a given list of numbers, you define the circulant graph in that way. So different lists give different kinds of circulant graphs. $\endgroup$– Guy Paterson-JonesNov 5, 2015 at 11:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Consider a graph $G$ with $n$ nodes. Now form any list $L=(L_1,L_2,...,L_{\lfloor n/2\rfloor})$ where the list contains true or false elements. Let $N=\{{N_0,N_1,...,N_{n-1}}\}$ detone the nodes in $G$. Then the graph $G$ is circulant iff its set of edges is $$ \{{{\{N_i,N_j\}}\,|\,L_k\text{ is true},\,0\le i<n,\,(i+k)\;\text mod\; n = j}\}. $$
-
$\begingroup$ Thanks for the answer. But do we always have $\lfloor n/2 \rfloor$ number of elements in the list $L$? Can it be fewer or more than that? $\endgroup$– monalisaNov 6, 2015 at 6:05
-
$\begingroup$ @monalisa This is not the original definition. I don't remember the origninal, but you could for example have a list $L=(L_1,L_2,...,L_n)$ where for all $L_i$: $L_i=L_{n+1-i}$. A shorter list would not work for this set of edges. $\endgroup$ Nov 6, 2015 at 14:22