Balanced circulants

Given interer $k \geq 1$ and $m \geq 1$, let us introduce a graph $G(k,m) = (V,E)$ with circular symmetry as follows: $V = {\bf Z}_n = \{0,1,...,n-1\}$, where $n = 4km$, and $(i,j) \in E$ iff

$$i-j + 4mt = +1 \;\; or \, -1 \;\; (mod \; n)$$

for some integer $t$. E.g. if $k=5, m=2$ then $n = 40$ and $(i,j) \in E$ iff $i - j (mod \; 40) \in \{7,9; 15,17; 23,25; 31,33; 39,1\}.$

It is not difficult to check that $G(k,m)$ is balanced, i.e. it has no odd cycles, nor $(4i+2)$-holes. In fact, it may only contain holes of length 4 and $4m$. Moreover, every $(4i+2)$-cycle has at least two chords. Hence, $G(k,m) - e$ is still balanced for any edge $e$, in agreement with Conjecture 2 from the section "Balanced Graphs". Conjecture 1 of the same section also holds for $G(k,m)$. Indeed, if $k > 1$ then $S = \{0; 4mi+1, 4mi-1 \; \vert \; i = 1, \ldots ,k\}$ is a star cutset: 0 is an isolated vertex in $\bar{G}[S]$, while $4mj$ is an isolated vertex in $G[V \setminus S]$ for every $j = 1, \ldots, k;$ and if $k=1$ then $G(k,m)$ is $4m$-cycle, that is a basic graph

CONJECTURE. Every non-empty balanced circulant is isomorphic to a $G(k,m)$.

Contributed by Diogo Andrade, Endre Boros, and Vladimir Gurvich

Back to the main index for Perfect Graphs.