Browse Prior Art Database

GROUPS ACTING ON REGULAR GRAPHS AND GROUP AMALGAMS

IP.com Disclosure Number: IPCOM000128611D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 24 page(s) / 51K

Publishing Venue

Software Patent Institute

Related People

Dragamir Z. Djokovic: AUTHOR [+4]

Abstract

The s-transitive groups acting on connected regular graphs have been studied by several people: W.T. Tutte, A. Gardiner, N. Biggs, R.M. Weiss, the authors and others. The purpose of this paper is two-fold. First we establish that the problems about constructing and existence of such groups have a simple purely group-theoretical formulation in terms of group amalgams. Second, we determine the group amalgams associated with the locally regular groups operating on cubic graphs. In Section 1 we introduce graph-theoretical concepts that we need and in Section 2 the basic definitions about group amalgams. Section 3 explains the connection between .l-transitive groups and group amalgams. Section 4 classifies finite simple amalgams of degree (3,2). It is surprising (Theorem 4) that there are precisely 7 such amalgams. Section 5 expresses some known results about s-transitive groups in the language of group amalgams. Section 7 explains the connection between locally 1-transitive groups and group amalgams. The next two sections deal with the amalgams associated to locally regular groups acting on cubic graphs. We show that there is essentially only one such amalgam for locally s-

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 24

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

GROUPS ACTING ON REGULAR GRAPHS AND GROUP AMALGAMS

Dragamir Z. Djokovic Department of Pure Mathematics University of Waterloo

Gary L. Miller Departments of Mathematics and Computer Science The University of Rochester

TR24 The work of the first author was supported in part by NRC Grant A-5285, and that of the second author by NRC Grant A-5549. . Groups Acting on Regular 'Graphs and Group Amalgams

v Dragomir Z. Djokovic and Gary L. Miller

0. INTRODUCTION

The s-transitive groups acting on connected regular graphs have been studied by several people: W.T. Tutte, A. Gardiner, N. Biggs, R.M. Weiss, the authors and others. The purpose of this paper is two-fold. First we establish that the problems about constructing and existence of such groups have a simple purely group-theoretical formulation in terms of group amalgams. Second, we determine the group amalgams associated with the locally regular groups operating on cubic graphs. In Section 1 we introduce graph-theoretical concepts that we need and in Section 2 the basic definitions about group amalgams. Section 3 explains the connection between .l-transitive groups and group amalgams. Section 4 classifies finite simple amalgams of degree (3,2). It is surprising (Theorem 4) that there are precisely 7 such amalgams. Section 5 expresses some known results about s-transitive groups in the language of group amalgams. Section 7 explains the connection between locally 1-transitive groups and group amalgams. The next two sections deal with the amalgams associated to locally regular groups acting on cubic graphs. We show that there is essentially only one such amalgam for locally s- -

regular groups s = 1,2,3,4,5, or 7. We end with two remarks, in the last section, which illustrate the usefullness of the graph-theoretical method in the study of group amalgams.

I. GROUPS ACTING ON GRAPHS

' Let G be a graph having neither loops nor multiple edges. Let A be a group and f:A -* Aut(G) a homomorphism. Then we say that A acts on G and we write f(a)(x) = a*x for a e A and x a vertex of G. If f is injective we say that the action is faithful and in that case we may consider A as a subgroup of Aut(G). From now on we consider a pair (G,A) where G is a connected graph and A a .subgroup of Aut(G). Recall that an s-arc S of G is a map

(Equation Omitted)

(V(G) = the vertex-set of G) such that S(i) and S(i + 1) are adjacent

for

(Equation Omitted)

Columbia University Page 1 Dec 31, 1979

Page 2 of 24

GROUPS ACTING ON REGULAR GRAPHS AND GROUP AMALGAMS

. w We say that A is s-transitive (resp. locally s-transitive) w if given any two s-arcs S1 and S2 (resp. two s-arcs Sl and S2 satisfying

(Equation Omitted)

there exists oc e A such that a

(Equation Omitted)

If A is locally s-transitive (s ? 1) then A acts transitively on the set of edges of G [1, Lemma 1]. Thus, in this case, A is either transitive on V or it has precisely two orbits, say V+ and V-, an...