# definition clarification of some special type of graphs

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

• 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. – Guy Paterson-Jones Nov 5 '15 at 11:29

## 1 Answer

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

• 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? – monalisa Nov 6 '15 at 6:05
• @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. – Niklas Bäckström Nov 6 '15 at 14:22