Given interer and , let us introduce a graph with circular symmetry as follows: , where , and iff

for some integer . E.g. if then and iff

It is not difficult to check that is balanced, i.e. it has no odd cycles, nor -holes. In fact, it may only contain holes of length 4 and . Moreover, every -cycle has at least two chords. Hence, is still balanced for any edge , in agreement with Conjecture 2 from the section "Balanced Graphs". Conjecture 1 of the same section also holds for . Indeed, if then is a star cutset: 0 is an isolated vertex in , while is an isolated vertex in for every and if then is -cycle, that is a basic graph

CONJECTURE. Every non-empty balanced circulant is isomorphic to a .

Contributed by Diogo Andrade, Endre Boros, and Vladimir Gurvich

Back to the
main index
for Perfect Graphs.