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.


  • 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$ Nov 5, 2015 at 11:29

1 Answer 1


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$
    – monalisa
    Nov 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.