d‐homogeneous and d‐ultrahomogeneous linear spaces

A linear space S is d‐homogeneous if, whenever the linear structures induced on two subsets S₁ and S₂ of cardinality at most d are isomorphic, there is at least one automorphism of S mapping S₁ onto S₂. S is called d‐ultrahomogeneous if each isomorphism between the linear structures induced on two subsets of cardinality at most d can be extended into an automorphism of S. We have proved in [11;] (without any finiteness assumption) that every 6‐homogeneous linear space is homogeneous (that is d‐homogeneous for every positive integer d). Here we classify completely the finite nontrivial linear spaces that are d‐homogeneous for d ≥ 4 or d‐ultrahomogeneous for d ≥ 3. We also prove an existence theorem for infinite nontrivial 4‐ultrahomogeneous linear spaces. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 321–329, 2000     

An infinite family of biprimitive semisymmetric graphs

A regular and edge-transitive graph that is not vertex-transitive is said to be semisymmetric. Every semisymmetric graph is necessarily bipartite, with the two parts having equal size and the automorphism group acting transitively on each of these two parts. A semisymmetric graph is called biprimitive, if its automorphism group acts primitively on each part. In this article, a classification of biprimitive semisymmetric graphs arising from the action of the group PSL(2, p), p ≡ ±1 (mod 8) a prime, acting on cosets of S₄ is given, resulting in several new infinite families of biprimitive semisymmetric graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 217–228, 1999     

Resolutions of PG(5, 2) with point‐cyclic automorphism group

A t‐(υ, k, λ) design is a set of υ points together with a collection of its k‐subsets called blocks so that all subsets of t points are contained in exactly λ blocks. The d‐dimensional projective geometry over GF(q), PG(d, q), is a 2‐(q^d + q^d−1 + … + q + 1, q + 1, 1) design when we take its points as the points of the design and its lines as the blocks of the design. A 2‐(υ, k, 1) design is said to be resolvable if the blocks can be partitioned as ℛ = {R₁, R₂, …, R_s}, where s = (υ − 1)/(k−1) and each R_i consists of υ/k disjoint blocks. If a resolvable design has an automorphism σ which acts as a cycle of length υ on the points and ℛ^σ = ℛ, then the design is said to be point‐cyclically resolvable. The design associated with PG(5, 2) is known to be resolvable and in this paper, it is shown to be point‐cyclically resolvable by enumerating all inequivalent resolutions which are invariant under a cyclic automorphism group G = 〈σ〉 where σ is a cycle of length 63. These resolutions are the only resolutions which admit a point‐transitive automorphism group. Furthermore, some necessary conditions for the point‐cyclic resolvability of 2‐(υ, k, 1) designs are also given. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 2–14, 2000     

Tricyclic Steiner Triple Systems

A Steiner triple system of order ν, denoted STS(ν), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this paper we give necessary and sufficient conditions for the existence of a tricyclic STS(ν) for several cases. We also pose conjectures concerning their existence in two remaining cases.     

A recursive construction of 1-rotational Steiner 2-designs

A Steiner 2-design S(2,k, v) is said to be 1-rotational if it admits an automorphism whose cycle structure is a (v ? 1)-cycle and a fixed point. In this paper, a recursive construction of 1-rotational Steiner 2-designs is given.     

Some rigid Steiner 5‐designs

Hitherto, all known non‐trivial Steiner systems S(5, k, v) have, as a group of automorphisms, either PSL(2, v−1) or PGL(2, (v−2)/2) × C₂. In this article, systems S(5, 6, 72), S(5, 6, 84) and S(5, 6, 108) are constructed that have only the trivial automorphism group. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:392–400, 2010     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

Cycle structures of automorphisms of 2-(v,k,1) designs

An automorphism of a 2?(v,k, 1) design acts as a permutation of the points and as another of the blocks. We show that the permutation of the blocks has at least as many cycles, of lengths n > k, as the permutation of the points. Looking at Steiner triple systems we show that this holds for all n unless n|Cp(n)| ? 3, where Cp(n) is the set of cycles of length n of the automorphism in its action on the points. Examples of Steiner triple systems for each of these exceptions are given. Considering designs with infinitely many points, but with k finite, we show that these results generalize. © 1995 John Wiley & Sons, Inc.     

On making two Steiner triple systems disjoint

We prove that if (S₁, β₁) and (S₂, β₂) are two Steiner triple systems of order v and if S is a set of v points, then there exist two disjoint Steiner triple systems (S, β₁′) and (S, β₂′) with (S₁, β₁) ? (S, β₁′) and (S₂, β₂) ? (S, β₂′).     

Direct products of automorphism groups of graphs

In this article we study the product action of the direct product of automorphism groups of graphs. We generalize the results of Watkins [J. Combin Theory 11 (1971), 95–104], Nowitz and Watkins [Monatsh. Math. 76 (1972), 168–171] and W. Imrich [Israel J. Math. 11 (1972), 258–264], and we show that except for an infinite family of groups S_n × S_n, n≥2 and three other groups D₄ × S₂, D₄ × D₄ and S₄ × S₂ × S₂, the direct product of automorphism groups of two graphs is itself the automorphism group of a graph. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 26–36, 2009     

Ubiquitous configurations in Steiner triple systems

A Steiner triple system S is a C-ubiquitous (where C is a configuration) if every line of S is contained in a copy of C, and is n-ubiquitous if it is C-ubiquitous for every n-line configuration C. We determine the spectrum of 4-ubiquitous Steiner triple systems as well as the spectra of C-ubiquitous Steiner triple systems for all configurations C with five lines. © 1997 John Wiley & Sons, Inc.     

Arbitrary groups as two-point stabilisers of symmetric groups acting on partitions

We give a short, direct proof that given any finite group G there exist positive integers k and l and partitions α₁and α₂ of {1, …, kl } into l subsets of size k such that (S _kl ) _{α 1}, _{α 2}≅ G.The method used will also show that given any finite group G there exists a regular bipartite graph whose automorphism group is isomorphic to G     

Intersections among Steiner systems

A Steiner system S(l, m, n) is a system of subsets of size m (called blocks) from an n-set S, such that each d-subset from S is contained in precisely one block. Two Steiner systems have intersection k if they share exactly k blocks. The possible intersections among S(5, 6, 12)'s, among S(4, 5, 11)'s, among S(3, 4, 10)'s, and among S(2, 3, 9)'s are determined, together with associated orbits under the action of the automorphism group of an initial Steiner system. The following are results: (i) the maximal number of mutually disjoint S(5, 6, 12)'s is two and any two such pairs are isomorphic; (ii) the maximal number of mutually disjoint S(4, 5, 11)'s is two and any two such pairs are isomorphic; (iii) the maximal number of mutually disjoint S(3, 4, 10)'s is five and any two such sets of five are isomorphic; (iv) a result due to Bays in 1917 that there are exactly two non-isomorphic ways to partition all 3-subsets of a 9-set into seven mutually disjoint S(2, 3, 9)'s.     

1‐Rotational Steiner triple systems over arbitrary groups

Phelps and Rosa introduced the concept of 1‐rotational Steiner triple system, that is an STS(ν) admitting an automorphism consisting of a fixed point and a single cycle of length ν ? 1 [Discrete Math. 33 ( 12 ), 57–66]. They proved that such an STS(ν) exists if and only if ν ≡ 3 or 9 (mod 24). Here, we speak of a 1‐rotational STS(ν) in a more general sense. An STS(ν) is 1‐rotational over a group G when it admits G as an automorphism group, fixing one point and acting regularly on the other points. Thus the STS(ν)'s by Phelps and Rosa are 1‐rotational over the cyclic group. We denote by ??_1r, ??_1r, ??_1r, ??_1r, the spectrum of values of ν for which there exists a 1‐rotational STS(ν) over an abelian, a cyclic, a dicyclic, and an arbitrary group, respectively. In this paper, we determine ??_1r and find partial answers about ??_1r and ??_1r. The smallest 1‐rotational STSs have orders 9, 19, 25 and are unique up to isomorphism. In particular, the only 1‐rotational STS(25) is over SL₂(3), the special linear group of dimension 2 over Z₃. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 215–226, 2001     

On Isomorphisms of Finite Cayley Graphs

A Cayley graph Cay(G,S) of a groupGis called a CI-graph if wheneverTis another subset ofGfor which Cay(G,S) Cay(G,T), there exists an automorphism σ ofGsuch thatS^σ = T. For a positive integerm, the groupGis said to have them-CI property if all Cayley graphs ofGof valencymare CI-graphs; further, ifGhas thek-CI property for allk ≤ m, thenGis called anm-CI-group, and a |G|-CI-groupGis called a CI-group. In this paper, we prove that Ais not a 5-CI-group, that SL(2,5) is not a 6-CI-group, and that all finite 6-CI-groups are soluble. Then we show that a nonabelian simple group has the 4-CI property if and only if it is A₅, and that no nonabelian simple group has the 5-CI property. Also we give nine new examples of CI-groups of small order, which were found to be CI-groups with the assistance of a computer.     

Embeddable anticonformal automorphisms of Riemann surfaces

Let S be a Riemann surface and f be an automorphism of finite order of S. We call f embeddable if there is a conformal embedding such that is the restriction to e(S) of a rigid motion. In this paper we show that an anticonformal automorphism of finite order is embeddable if and only if it belongs to one of the topological conjugation classes here described. For conformal automorphisms a similar result was known by R.A. Rüedy [R3]. Received: February 8, 1996     

On the Antipode of a Co-Frobenius (Co)Quasitriangular Hopf Algebra

For H a quasitriangular Hopf algebra, S ², the square of the antipode is the inner automorphism induced by the Drinfeld element u, and S ⁴ is the inner automorphism induced by the grouplike element g = uS(u)^?1. For H finite dimensional, results of Drinfeld and Radford express g in terms of the modular elements of H. This note supplies another proof which replaces the requirement of finite dimensionality with existence of a nonzero integral for H in H*. Similar results hold for the infinite dimensional coquasitriangular case; here we supply some interesting examples.     

The nonexistence of a certain Steiner system S(3, 12, 112)

Although the automorphism group of a projective plane of order 10, if one exists, must be very small, such a plane could be the derived design of a Steiner system S(3, 12, 112) with a larger group. There are several reasons why the Frobenius group of order 56 is a promising candidate for the latter group. However, in this paper it is shown that there is no S(3, 12, 112) which is fixed by this Frobenius group.     

Constructions for rotational Steiner quadruple systems

A direct construction for rotational Steiner quadruple systems of order p+ 1 having a nontrivial multiplier automorphism is presented, where p≡13 (mod24) is a prime. We also give two improved product constructions. By these constructions, the known existence results of rotational Steiner quadruple systems are extended. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 353–368, 2009     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory