0
$\begingroup$

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.

http://mathworld.wolfram.com/CirculantGraph.html

|cite|improve this question
$\endgroup$
  • 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-Jones Nov 5 '15 at 11:29
2
$\begingroup$

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}\}. $$

|cite|improve this answer
$\endgroup$
  • $\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 '15 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$ – Niklas Bäckström Nov 6 '15 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.