Following Hujdurović et al. (2016), an automorphism of a graph is said to be even/odd if it acts on the vertex set of the graph as an even/odd permutation. In this paper the formula for calculating the number of graphs of order n admitting odd automorphisms and the formula for calculating the number of graphs of order n without odd automorphisms are given together with their asymptotic estimates. The so-called VTO numbers are also defined.
COBISS.SI-ID: 1540253636
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
Tetravalent graphs admitting a half-arc-transitive subgroup of automorphisms, that is a subgroup acting transitively on its vertices and its edges but not on its arcs, are investigated. One of the most fruitful approaches for the study of structural properties of such graphs is the well known paradigm of alternating cycles and their intersections which was introduced by the PI 20 years ago. In this paper a new parameter for such graphs, giving a further insight into their structure, is introduced.
COBISS.SI-ID: 1540554436
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