An automorphism of a graph is said to be even/odd if it acts on the set of vertices as an even/odd permutation. In this article we pose the problem of determining which vertex-transitive graphs admit odd automorphisms. Partial results for certain classes of vertex-transitive graphs, in particular for Cayley graphs, are given. As a consequence, a characterization of arc-transitive circulants without odd automorphisms is obtained.
COBISS.SI-ID: 1538542276
An automorphism α of a Cayley graph Cay(G,S) of a group G is color-preserving if α(g,gs) = (h,hs) or (h, hs−1) for every edge (g,gs)∈E(Cay(G,S)). If every color-preserving automorphism of Cay(G,S) is also affine, then Cay(G,S) is a CCA (Cayley color automorphism) graph. If every Cayley graph Cay(G,S) is a CCA graph, then G is a CCA group. In this paper it is shown that there is a unique non-CCA Cayley graph X of the non-abelian group F21 of order 21. It is also shown that if Cay(G,S) is a non-CCA graph of a group G of odd square-free order, then G = H×F21 for some CCA group H, and Cay(G,S) is a Cartesian product of Cay(H,T) and X.
COBISS.SI-ID: 1538755268
Let G denote a bipartite distance-regular graph with diameter D \ge 4 and valency k \ge 3. Let X denote the vertex set of G, and let A denote the adjacency matrix of G. Define a parameter Delta_2 in terms of the intersection numbers by Delta_2 = (k-2)(c_3-1)-(c_2-1)p^2_{22}. We first show that Delta_2 = 0 implies that D \le 5 or c_2 is either 1 or 2. In this paper we assume c_2=1. Under some additional assumptions we study the Terwilliger algebra T of graph G. We show that if G is not almost 2-homogeneous, then up to isomorphism there exists exactly one irreducible T-module with endpoint 2. We give an orthogonal basis for this T-module, and we give the action of A on this basis.
COBISS.SI-ID: 1538163396