An explicit characterization of cubic symmetric bi-Cayley graphs on nonabelian simple groups

One of the remarkable contributions in the study of symmetric Cayley graphs on nonabelian simple groups is the complete classification of such graphs that are cubic and nonnormal. This naturally motivates the study of cubic (normal and nonnormal) symmetric bi-Cayley graphs on nonabelian simple groups. In this paper, the full automorphism groups of these graphs are determined, and necessary and sufficient conditions are given for a graph being a cubic normal symmetric Cayley or bi-Cayley graph on a nonabelian simple group (one may then find many examples). As an application, we also prove that cubic symmetric Cayley graphs on nonabelian simple groups are stable.     

Automorphism groups of cyclic codes

In this article we study the automorphism groups of binary cyclic codes. In particular, we provide explicit constructions for codes whose automorphism groups can be described as (a) direct products of two symmetric groups or (b) iterated wreath products of several symmetric groups. Interestingly, some of the codes we consider also arise in the context of regular lattice graphs and permutation decoding.     

Superrigidity of Hyperbolic Buildings

In this paper, we study the behavior of harmonic maps into complexes with branching differentiable manifold structure. The main examples of such target spaces are Euclidean and hyperbolic buildings. We show that a harmonic map from an irreducible symmetric space of noncompact type other than real or complex hyperbolic into these complexes are non-branching. As an application, we prove rank-one and higher-rank superrigidity for the isometry groups of a class of complexes which includes hyperbolic buildings as a special case.     

Reaction Graphs

Chemical reaction graphs (for a fixed type of rearrangement) are orbital graphs for transitive permutation representations of symmetric groups, so algebraic combinatorics and group theory are effective tools for studying such properties as their connectivity and automorphisms. For example, we construct orbital graphs (and, hence, reaction graphs) from Cayley diagrams by contracting edges, and use graph-embeddings in surfaces to determine the automorphism groups of these graphs. We apply these ideas to the rearrangements of the P ₇ ^3- -ion and of bullvalene, together with some purely mathematical examples of reaction graphs.     

Partial difference sets and amorphic Cayley schemes in non‐abelian 2‐groups

In this paper, we consider regular automorphism groups of graphs in the RT2 family and the Davis‐Xiang family and amorphic abelian Cayley schemes from these graphs. We derive general results on the existence of non‐abelian regular automorphism groups from abelian regular automorphism groups and apply them to the RT2 family and Davis‐Xiang family and their amorphic abelian Cayley schemes to produce amorphic non‐abelian Cayley schemes.     

Pentavalent symmetric graphs of order 2p3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.     

Covering theory for complexes of groups

We develop an explicit covering theory for complexes of groups, parallel to that developed for graphs of groups by Bass. Given a covering of developable complexes of groups, we construct the induced monomorphism of fundamental groups and isometry of universal covers. We characterize faithful complexes of groups and prove a conjugacy theorem for groups acting freely on polyhedral complexes. We also define an equivalence relation on coverings of complexes of groups, which allows us to construct a bijection between such equivalence classes, and subgroups or overgroups of a fixed lattice Γ in the automorphism group of a locally finite polyhedral complex X.     

Main eigenvalues and automorphisms of a graph

We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs.     

Main eigenvalues and automorphisms of a graph

We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs.     

Topology of matching,chessboard, and general bounded degree graph complexes

We survey results and techniques in the topological study of simplicial complexes of (di-, multi-, hyper-)graphs whose node degrees are bounded from above. These complexes have arisen in a variety of contexts in the literature. The most well-known examples are the matching complex and the chessboard complex. The topics covered here include computation of Betti numbers, representations of the symmetric group on rational homology, torsion in integral homology, homotopy properties, and connections with other fields.In memory of Gian-Carlo Rota     

On balanced Cayley maps over abelian groups

A notion of a balanced automorphism of a group was introduced in [J. Sirǎn and M. Skoviera. Regular maps from Cayley graphs. I. Balanced Cayley maps. Algebraic graph theory (Leibnitz, 1989). Discrete Math. 109 (1992), no. 1–3, 265–276] in order to study regular Cayley maps over finite groups. One of the open questions formulated in the paper was this: which finite abelian groups admit a balanced automorphism? The presented paper answers this question.     

Ternary codes from the strongly regular (45, 12, 3, 3) graphs and orbit matrices of 2-(45, 12, 3) designs

The enumeration of strongly regular graphs with parameters (45, 12, 3, 3) has been completed, and it is known that there are 78 non-isomorphic strongly regular (45, 12, 3, 3) graphs. A strongly regular graph with these parameters is a symmetric (45, 12, 3) design having a polarity with no absolute points. In this paper we examine the ternary codes obtained from the adjacency (resp. incidence) matrices of these graphs (resp. designs), and those of their corresponding derived and residual designs. Further, we give a generalization of a result of Harada and Tonchev on the construction of non-binary self-orthogonal codes from orbit matrices of block designs under an action of a fixed-point-free automorphism of prime order. Using the generalized result we present a complete classification of self-orthogonal ternary codes of lengths 12, 13, 14, and 15, obtained from non-fixed parts of orbit matrices of symmetric (45, 12, 3) designs admitting an automorphism of order 3. Several of the codes obtained are optimal or near optimal for the given length and dimension. We show in addition that the dual codes of the strongly regular (45, 12, 3, 3) graphs admit majority logic decoding.     

I‐graphs and the corresponding configurations

We consider the class of I‐graphs I(n,j,k), which is a generalization over the class of the generalized Petersen graphs. We study different properties of I‐graphs, such as connectedness, girth, and whether they are bipartite or vertex‐transitive. We give an efficient test for isomorphism of I‐graphs and characterize the automorphism groups of I‐graphs. Regular bipartite graphs with girth at least 6 can be considered as Levi graphs of some symmetric combinatorial configurations. We consider configurations that arise from bipartite I‐graphs. Some of them can be realized in the plane as cyclic astral configurations, i.e., as geometric configurations with maximal isometric symmetry. © 2005 Wiley Periodicals, Inc.     

Star clusters in independence complexes of graphs

We introduce the notion of star cluster of a simplex in a simplicial complex. This concept provides a general tool to study the topology of independence complexes of graphs. We use star clusters to answer a question arisen from works of Engström and Jonsson on the homotopy type of independence complexes of triangle-free graphs and to investigate a large number of examples which appear in the literature. We present an alternative way to study the chromatic and clique numbers of a graph from a homotopical point of view and obtain new results regarding the connectivity of independence complexes.     

Strongly regular graphs with non-trivial automorphisms

The possible existence of 16 parameter sets for strongly regular graphs with 100 or less vertices is still unknown. In this paper, we outline a method to search for strongly regular graphs by assuming a non-trivial automorphism of prime order. Among these unknown parameter sets, we eliminated many possible automorphisms, but some small prime orders still remain. We also found 6 new strongly regular graphs with parameters (49,18,7,6).     

Automorphisms of symmetric groups are toy examples for mapping class groups

We give a new proof establishing the automorphism groups of the symmetric groups inspired by the analogous result of Ivanov for the extended mapping class group. As a key tool, we consider the actions on the Kneser graphs.     

Relation graphs of an association scheme based on attenuated spaces

The set of subspaces with a given dimension in an attenuated space has a structure of a symmetric association scheme, which is a generalization of both Grassmann schemes and bilinear forms schemes. In this paper, we focus on two families of relation graphs. Their full automorphism groups are completely determined. As a consequence, the classical results of the automorphism groups of Grassmann graphs and bilinear forms graphs are generalized.     

On weakly symmetric graphs of order twice a prime

A graph is weakly symmetric if its automorphism group is both vertex-transitive and edge-transitive. In 1971, Chao characterized all weakly symmetric graphs of prime order and showed that such graphs are also transitive on directed edges. In this paper we determine all weakly symmetric graphs of order twice a prime and show that these graphs too are directed-edge transitive.     

Orderly generation of half-regular symmetric designs via Rahilly families of pre-difference sets

Rahilly families of pre-difference sets have been introduced by Rahilly, Praeger, Street and Bryant as a tool for constructing symmetric designs. Using orderly generation, we construct Rahilly families for various groups up to equivalence. For each equivalence class we determine the isomorphism type of the corresponding design. Some designs may be new, whilst others were already known in which case we identify them. For each design we test whether it admits as an automorphism group a regular extension of one of the given groups. If this is the case, the pre-difference set for the given group is also a difference set for the regular extension. We prove that there are examples of designs with a Rahilly family of pre-difference sets for a group which do not admit a regular extension.