Consider three integers $n,a,b$ such that $n>0$, $a \neq 0$, and $b \neq 0$. The simple undirected graph $C_n(a,b)=(V,E)$ where $V = \{v_0, v_1, \dots, v_{n-1}\}$ and $E = \{(v_i,v_{(i+a)\bmod n})$, $ (v_i,v_{(i+b)\bmod n})$, for $i=0, \dots, n-1 )\}$ is called circulant graph. In this contribution we shall consider only circulant graphs which are 4-regular and connected. We define a simple combinatorial model for the graphs, and investigate on some characteristic cycles of them. We propose a necessary and sufficient condition for two graphs in this class to be isomorphic. The result shows that the \'Ad\'am conjecture is true on the studied class of 4-regular and connected circulant graphs. The condition can also be used to easily generate all the circulant graphs isomorphic to a given one.
On Isomorphic 4-Regular Circulant Graphs
NICOLOSO Sara;
2006
Abstract
Consider three integers $n,a,b$ such that $n>0$, $a \neq 0$, and $b \neq 0$. The simple undirected graph $C_n(a,b)=(V,E)$ where $V = \{v_0, v_1, \dots, v_{n-1}\}$ and $E = \{(v_i,v_{(i+a)\bmod n})$, $ (v_i,v_{(i+b)\bmod n})$, for $i=0, \dots, n-1 )\}$ is called circulant graph. In this contribution we shall consider only circulant graphs which are 4-regular and connected. We define a simple combinatorial model for the graphs, and investigate on some characteristic cycles of them. We propose a necessary and sufficient condition for two graphs in this class to be isomorphic. The result shows that the \'Ad\'am conjecture is true on the studied class of 4-regular and connected circulant graphs. The condition can also be used to easily generate all the circulant graphs isomorphic to a given one.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
