Automorphisms of Cayley graphs

The aim of this paper is to characterize subgroups of non-regular automorphism groups of Cayley graphs. Relations between group automorphisms, graph automorphisms and permutations of the edge set of Cayley graphs are investigated.     

Automorphisms of imbedded graphs

If a linear graph is imbedded in a surface to form a map, then the map has a group of automorphisms which is a subgroup (usually, a proper subgroup) of the automorphism group of the graph. In this note it will be shown that, for any imbedding of K_n in an orientable surface, the order of the automorphism group of the resulting map is a divisor of n(n − 1), and that the order equals n(n − 1) if and only if n is a prime power. The explicit construction of imbeddings of K_Q, q = p^m with map automorphism group of order q(q − 1) gives rise to new types of regular map. There are also tenous connections with the theory of Frobenius groups.     

Automorphisms of graphs and coverings

We apply the theory of covering spaces to show how one can construct infinitely many finite s-transitive or locally s-transitive graphs. N. Biggs has used for similar purpose a special graph covering construction due to J. H. Conway.     

Spectrum of Johnson graphs

In this paper we prove new bounds on the second eigenvalue of Johnson graphs. We then apply these bounds to obtain new results on the modularity of Johnson graphs and their random subgraphs, hamiltonicity of Johnson graphs and thresholds of the appearance of the Hamilton cycles and giant components. Furthermore, we provide general bounds on vertex connectivity and the stability of the modularity for $(n,d,\lambda )$-graphs.     

Primitive decompositions of Johnson graphs

A transitive decomposition of a graph is a partition of the edge set together with a group of automorphisms which transitively permutes the parts. In this paper we determine all transitive decompositions of the Johnson graphs such that the group preserving the partition is arc-transitive and acts primitively on the parts.     

Isometric embeddings of Johnson graphs in Grassmann graphs

Let V be an n-dimensional vector space (4≤n<∞) and let G_k(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ _k (V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ _k (V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ _k (V) is an apartment of G_k(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ _k (V), 1<k<n−1.     

Homogeneous factorisations of Johnson graphs

For a graph Γ, subgroups , and an edge partition of Γ, the pair is a (G, M)-homogeneous factorisation if M is vertex-transitive on Γ and fixes setwise each part of , while G permutes the parts of transitively. A classification is given of all homogeneous factorisations of finite Johnson graphs. There are three infinite families and nine sporadic examples. This paper forms part of an ARC Discovery grant of the last two authors. The second author holds an Australian Research Council Australian Research Fellowship.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Neighbour-transitive codes in Johnson graphs

The Johnson graph \(J(v,k)\) has, as vertices, the \(k\) -subsets of a \(v\) -set \(\mathcal {V}\) and as edges the pairs of \(k\) -subsets with intersection of size \(k-1\) . We introduce the notion of a neighbour-transitive code in \(J(v,k)\) . This is a proper vertex subset \(\Gamma \) such that the subgroup \(G\) of graph automorphisms leaving \(\Gamma \) invariant is transitive on both the set \(\Gamma \) of ‘codewords’ and also the set of ‘neighbours’ of \(\Gamma \) , which are the non-codewords joined by an edge to some codeword. We classify all examples where the group \(G\) is a subgroup of the symmetric group \(\mathrm{Sym}\,(\mathcal {V})\) and is intransitive or imprimitive on the underlying \(v\) -set \(\mathcal {V}\) . In the remaining case where \(G\le \mathrm{Sym}\,(\mathcal {V})\) and \(G\) is primitive on \(\mathcal {V}\) , we prove that, provided distinct codewords are at distance at least \(3\) , then \(G\) is \(2\) -transitive on \(\mathcal {V}\) . We examine many of the infinite families of finite \(2\) -transitive permutation groups and construct surprisingly rich families of examples of neighbour-transitive codes. A major unresolved case remains.     

Automorphisms of infinite dimensional Lie algebras of Cartan type

In this paper it is proved that any automorphism of an infinite dimensional Lie algebra of Cartan type over an algebraically closed field of characteristicp>2 can be induced from an automorphism of the associated divided power algebra.     

Invariant Hamming graphs in infinite quasi-median graphs

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming graph.     

Strongly perfect infinite graphs

An infinite graph G is calledstrongly perfect if each induced subgraph ofG has a coloring (C _i :i ∈I) and a clique meeting each colorC _i . A conjecture of the first author and V. Korman is that a perfect graph with no infinite independent set is strongly perfect. We prove the conjecture for chordal graphs and for their complements. The research was begun at the Sonderforschungsbereich 343 at Bielefeld University and supported by the Fund for the Promotion of Research at the Technion.     

Automorphisms with only infinite orbits on non-algebraic elements

 This paper generalizes results of F. K?rner from [4] where she established the existence of maximal automorphisms (i.e. automorphisms moving all non-algebraic elements). An ω-maximal automorphism is an automorphism whose powers are maximal automorphisms. We prove that any structure has an elementary extension with an ω-maximal automorphism. We also show the existence of ω-maximal automorphisms in all countable arithmetically saturated structures. Further we describe the pairs of tuples (ˉa,ˉb) for which there is an ω-maximal automorphism mapping ˉa to ˉb. Received: 12 December 2001 / Published online: 10 October 2002 Supported by the ``Fonds pour la Formation à la Recherche dans l'Industrie et dans l'Agriculture' Mathematics Subject Classification (2000): Primary: 03C50; Secondary: 03C57 Key words or phrases: Automorphism – Recursively saturated structure