On infinite tournaments with regular automorphism groups

Atournament regular representation (TRR) of an abstract groupG is a tournamentT whose automorphism group is isomorphic toG and is a regular permutation group on the vertices ofT. L. Babai and W. Imrich have shown that every finite group of odd order exceptZ ₃ ×Z ₃ admits a TRR. In the present paper we give several sufficient conditions for an infinite groupG with no element of order 2 to admit a TRR. Among these are the following: (1)G is a cyclic extension byZ of a finitely generated group; (2)G is a cyclic extension byZ _2n+1 of any group admitting a TRR; (3)G is a finitely generated abelian group; (4)G is a countably generated abelian group whose torsion subgroup is finite.     

ON CIRCULANT DIGRAPHS WITH REGULAR AUTOMORPHISM GROUPS

Abstract. We prove that the cyclic group Zn(n≥3) has a k-regular digraph regular     

Finite digraphs with given regular automorphism groups

With five exceptions, every finite regular permutation group occurs as the automorphism group of a digraph.One of the corollaries: given a finite groupG of ordern, there is a commutative semigroupS of order 2n+2 such that AutSG. The problem whether a latticeL of order Cn with AutLG exists (for some constantC), remains open.     

On the full automorphism group of a graph

While it is easy to characterize the graphs on which a given transitive permutation groupG acts, it is very difficult to characterize the graphsX with Aut (X)=G. We prove here that for the certain transitive permutation groups a simple necessary condition is also sufficient. As a corollary we find that, whenG is ap-group with no homomorphism ontoZ _p wrZ _p , almost all Cayley graphs ofG have automorphism group isomorphic toG.     

On automorphism groups of Cayley graphs

LetX _G,H denote the Cayley graph of a finite groupG with respect to a subsetH. It is well-known that its automorphism groupA(X_G,H) must contain the regular subgroupL _G corresponding to the set of left multiplications by elements ofG. This paper is concerned with minimizing the index [A(X_G,H)L_G] for givenG, in particular when this index is always greater than 1. IfG is abelian but not one of seven exceptional groups, then a Cayley graph ofG exists for which this index is at most 2. Nearly complete results for the generalized dicyclic groups are also obtained.     

Factorial regular representation of groups in complete graphs

A necessary and sufficient condition for the group of isomorphisms involved in a factorization of a complete graph into isomorphic factors is established.     

Graphs with prescribed degree sets and girth

For a finite nonempty set of integers, each of which is at least two, and an integern 3, the numberf(;n) is defined as the least order of a graph having degree set and girthn. The numberf(;n) is evaluated for several sets and integersn. In particular, it is shown thatf({3, 4}; 5) = 13 andf({3, 4}; 6) = 18.Research of the third author was partially supported by a Faculty Research Fellowship from Western Michigan University.     

Non rank 3 strongly regular graphs with the 5-vertex condition

Three new strongly regular graphs on 256, 120, and 135 vertices are described in this paper. They satisfy thet-vertex condition — in the sense of [1] — on the edges and on the nonedges fort=4 but they are not rank 3 graphs. The problem to search for any such graph was discussed on a folklore level several times and was fixed in [2]. Here the graph on 256 vertices satisfies even the 5-vertex condition, and has the graphs on 120 and 135 vertices as its subgraphs. The existence of these graphs was announced in [3] and [4]. [4] contains M. H. Klin's interpretation of the graph on 120 vertices. Further results concerning these graphs were obtained by A. E. Brouwer, cf. [5].     

Two spectral characterizations of regular, bipartite graphs with five eigenvalues

Graphs with a few distinct eigenvalues usually possess an interesting combinatorial structure. We show that regular, bipartite graphs with at most six distinct eigenvalues have the property that each vertex belongs to the constant number of quadrangles. This enables to determine, from the spectrum alone, the feasible families of numbers of common neighbors for each vertex with other vertices in its part. For particular spectra, such as [6,2⁹,0⁶,-2⁹,-6] (where exponents denote eigenvalue multiplicities), there is a unique such family, which makes it possible to characterize all graphs with this spectrum.Using this lemma we also to show that, for r?2, a graph has spectrum if and only if it is a graph of a 1-resolvable transversal design TD(r,r), i.e., if it corresponds to the complete set of mutually orthogonal Latin squares of size r in a well-defined manner.     

Polarities of G. Higman's symmetric design and a strongly regular graph on 176 vertices

We investigate the polarities of G. Higman's symmetric 2-(176, 50, 14) design and find that there are two of them (up to conjugacy), one having 80 and the other 176 absolute points. From the latter we can derive a strongly regular graph with parameters (v, k, , )=(176, 49, 12, 14). Its group of automorphisms is Sym(8) with orbits of size 8 and 168 on the vertices. It does not carry a partial geometry or a delta space, and is not the result of mergingd=1 andd=2 in a distance regular graph with diameter 3 and girth 6 on 176 vertices.     

Multiple periodic solutions of Hamiltonian systems with prescribed energy

Consider the periodic solutions of autonomous Hamiltonian systems on the given compact energy hypersurface Σ=H⁻¹(1). If Σ is convex or star-shaped, there have been many remarkable contributions for existence and multiplicity of periodic solutions. It is a hard problem to discuss the multiplicity on general hypersurfaces of contact type. In this paper we prove a multiplicity result for periodic solutions on a special class of hypersurfaces of contact type more general than star-shaped ones.     

The holomorphic automorphism group of the complex disk

The group of all holomorphic automorphisms of the complex unit disk consists of Möbius transformations involving translation-like holomorphic automorphisms and rotations. The former are calledgyrotranslations. As opposed to translations of the complex Plane, which are associative-commutative operations forming a group, gyrotranslations of the complex unit disk fail to form a group. Rather, left gyrotranslations are gyroassociative-gyrocommutative operations forming agyrogroup.     

Explicit construction of regular graphs without small cycles

For every integerd>2 we give an explicit construction of infinitely many Cayley graphsX of degreed withn(X) vertices and girth >0.4801...(logn(X))/log (d−1)−2. This improves a result of Margulis. Dedicated to Paul Erdős on his seventieth birthday     

Spin invariant theory for the symmetric group

We formulate a theory of invariants for the spin symmetric group in some suitable modules which involve the polynomial and exterior algebras. We solve the corresponding graded multiplicity problem in terms of specializations of the Schur Q-functions and a shifted q-hook formula. In addition, we provide a bijective proof for a formula of the principal specialization of the Schur Q-functions.     

Every group is the automorphism group of a rank-3 matroid

Every group is the automorphism group of a rank-3 extension of a rank-3 Dowling geometry.Partially supported by The George Washington University UFF grant.Partially supported by the National Security Agency under grant MDA904-91-H-0030.     

Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.