On Tetravalent Near-Bipartite Arc-Transitive Circulants

摘要

A graph Γ is said to be near-bipartite if there exists a subset of a vertex set of Γ with no adjacent vertices, such that its complement induces a bipartite graph. A circulant is a Cayley graph on a cyclic group. A graph is arc-transitive if its automorphism group acts transitively on the set of its arcs. In this paper a question which tetravalent arc-transitive circulants are near-bipartite is considered. In particular, it is shown that if the order of a tetravalent arc-transitive circulant has a prime divisor p > 13 such that 2p = (2s + l)~2 + 1 then it is near-bipartite. It is also shown that any tetravalent arc-transitive circulant of even order is near-bipartite.