%Latest version:30/11/98 %modified in September 1999 \documentclass[12pt, a4paper]{article} %\usepackage{uwamaths} \usepackage{amsmath} %\usepackage{eufrak} \usepackage{latexsym} %\usepackage{graphicx, float} \marginparwidth 0pt \oddsidemargin 0pt \evensidemargin 0pt \topmargin 0pt \textheight 21.0 truecm \textwidth 16.0 truecm \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}[theorem]{Definition} \newtheorem{problem}[theorem]{Problem} \newtheorem{example}[theorem]{Example} \newtheorem{construction}[theorem]{Construction} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{remark}[theorem]{Remark} \newtheorem{question}[theorem]{Question} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{comment}[theorem]{Comment} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}{Lemma} %\newtheorem{corollary}{Corollary} %\newtheorem{proposition}{Proposition} %\newtheorem{definition}{Definition} %\newtheorem{problem}{Problem} %\newtheorem{example}{Example} %\newtheorem{construction}{Construction} %\newtheorem{conjecture}{Conjecture} %\newtheorem{remark}{Remark} %\newtheorem{question}{Question} %\newtheorem{algorithm}{Algorithm} %\newtheorem{comment}{Comment} \input amssym.def \input amssym.tex \def\proof{\par\noindent{\bf Proof~~}} %\def\proof{\medskip\noindent\emph{Proof.}\quad} \def\qed{\ifmmode\square\else\nolinebreak\hfill$\square$\fi\par\vskip12pt} %\def\qed{\quad\emph{qed}\bigskip} \newcommand{\prop}{{\mathfrak{p}}} \newcommand{\nat}{{f}} \newcommand{\cV}{{\cal V}} \newcommand{\cE}{{\cal E}} \newcommand{\adj}{\sim} %\newcommand{\qed}{{\bf Proof}} %\newcommand{\qed}{{$\Box$}} %\newcommand{\Sym}{\mathrm{Sym}} \newcommand{\partition}{{\cal P}} \newcommand{\tx}{\tilde{x}} \newcommand{\Fr}{\mathfrak{F}} \newcommand{\Fvt}{{\cal F}} \newcommand{\tu}{\tilde{\mu}} \newcommand{\ledge}{\epsilon} \newcommand{\edge}{{\cal E}} \newcommand{\tv}{\tilde{\nu}} \newcommand{\ta}{\tilde{\alpha}} \newcommand{\tb}{\tilde{\beta}} \newcommand{\ty}{\tilde{y}} \newcommand{\te}{\tilde{e}} \newcommand{\tG}{\tilde{\Gamma}} \newcommand{\graphA}{\Delta} \newcommand{\graphB}{\Xi} \def\ov{\overline} \def\l{\langle} \def\r{\rangle} \def\tr{{\rm tr}} \def\div{\,\Big|\,} \def\notdiv{\,{\not\Big|}\,} \def\FFF{\Bbb F} \def\ZZZ{\Bbb Z} \def\NNN{\Bbb N} \def\PP{{\cal P}} \def\GG{{\cal G}} \def\BB{{\cal B}} \def\FB{{\cal LQ}} \def\C{{\bf C}} \def\N{{\bf N}} \def\Z{{\bf Z}} \def\O{{\bf O}} \def\Q{{\rm Q}} \def\D{{\rm D}} \def\A{{\rm A}} \def\S{{\rm S}} \def\L{{\rm L}} \def\Ga{\Gamma} \def\G{\Gamma} \def\a{\alpha} \def\b{\beta} \def\d{\delta} \def\g{\gamma} \def\s{\sigma} \def\t{\tau} \def\ve{\varepsilon} \def\vp{\varphi} \def\d{\delta} \def\Sym{{\rm Sym}} \def\Inn{{\rm Inn}} \def\Out{{\rm Out}} \def\Cay{{\rm Cay}} \def\Aut{{\rm Aut}} \def\soc{{\rm soc}} \def\wr{{\rm\,wr\,}} \def\Diag{{\rm Diag}} \def\Syl{{\rm Syl}} \def\PSL{{\rm PSL}} \def\PGL{{\rm PGL}} \def\SL{{\rm SL}} \def\GL{{\rm GL}} \def\AGL{{\rm AGL}} \def\GammaL{{\rm\Gamma L}} \def\AGammaL{{\rm A\Gamma L}} \def\U{{\rm U}} \def\PSp{{\rm PSp}} \def\Sp{{\rm Sp}} \def\PO{{\rm P\Omega}} \def\POmega{{\rm P\Omega}} \def\E{{\rm E}}% \def\F{{\rm F}} %\def\G{{\rm G}} \def\Sz{{\rm Sz}} \def\Ree{{\rm Ree}} \def\M{{\rm M}} \def\J{{\rm J}} \def\McL{{\rm McL}} \def\Ru{{\rm Ru}} \def\Ly{{\rm Ly}} \def\Co{{\rm Co}} \def\Fi{{\rm Fi}} \def\Th{{\rm Th}} \def\BM{{\rm BM }} \def\ON{{\rm O'N}} \def\HS{{\rm HS}} \def\Suz{{\rm Suz}} \def\He{{\rm He}} \def\HN{{\rm HN}} \def\HA{{\rm HA}} \def\AS{{\rm AS}} \def\TW{{\rm TW}} \def\PA{{\rm PA}} \title{Analysing group actions on finite arc-transitive graphs} \author{ Cheryl E.~Praeger\\ Department of Mathematics and Statistics\\ The University of Western Australia\\ Nedlands, Perth, WA 6907, Australia} \date{} \begin{document} \openup 1.0\jot \maketitle \begin{abstract} An approach to studying certain families of finite connected arc-transitive graphs is described. This involves identifying some of the graphs in the families as basic, and describing arbitrary graphs in the families as covers, or multicovers, of the basic graphs. This was motivated by the successful study of finite distance-transitive graphs, and has been successful in analysing the structure of finite $s$-arc-transitive graphs ($s\geq 2$), locally-primitive graphs, and locally-quasiprimitive graphs. For other families of finite arc-transitive graphs, where less symmetry is present, extra information of a geometrical nature can be helpful in analysing the graph structure; an alternative approach due to Gardiner and the author is then available. These two approaches will be discussed, and compared. Some applications and open problems are given. \end{abstract} \section{Locally quasiprimitive graphs} One of the most successful uses of group theory in analysing a class of finite graphs is that leading to the classification of the finite distance transitive graphs, which is now approaching completion, see~\cite{ivanov}. The suggestion that this classification might indeed be feasible comes from early work of Biggs and Smith~\cite{biggs, smith} which in a sense reduced the problem to the case of vertex-primitive distance transitive graphs. Applying the O'Nan-Scott Theorem for finite primitive permutation groups further reduced the vertex-primitive classification to the case where the automorphism group is almost simple or affine, see~\cite{psy}. However, for many other interesting families of finite arc-transitive graphs, it is not possible to describe the structure of arbitrary graphs in the family in terms of vertex-primitive graphs in the family. In order to describe such families of graphs, it is not sufficient to focus on the vertex-primitive members. Happily it turns out that some families of arc-transitive graphs possess a weaker property which allows certain members of the family, which we call ``basic" members, to play a similar role to that of the vertex-primitive distance-transitive graphs. That is to say, the structure of an arbitrary graph in the family may be described in terms of some of the basic graphs. One of the largest families of finite arc-transitive graphs which possesses one such property is the family $\FB$ of finite, locally-quasiprimitive, arc-transitive graphs. \medskip \noindent\textbf{Some notation:}\quad A {\em graph} $\Gamma = (V,E)$ consists of a set $V$ of vertices and a subset $E$ of unordered pairs from $V$, called edges. A group $G$ of permutations of a set $\Delta$ is said to be {\em quasiprimitive} if each non-trivial normal subgroup of $G$ is transitive on $\Delta$. For a graph $\Gamma$, and a group $G$ acting as a group of automorphisms of $\Gamma$ (not necessarily faithfully), we say that $\Gamma$ is $G$-{\em arc-transitive} if $G$ acts transitively on the arcs of $\Gamma$ ({\em arcs} being ordered pairs of vertices joined by an edge of $\Gamma$), and $G$-{\em locally-quasiprimitive} if, for each vertex $\alpha$, the stabiliser $G_{\alpha}$ is quasiprimitive in its action on the set $\Gamma(\alpha)=\{\beta: \{\a,\b\}\in E\}$ of {\em neighbours} of $\alpha$ in $\Gamma$. \begin{definition} \label{defn:F}{\rm Let $\FB$ be the family of those graphs $\Ga$ which are $G$-vertex-transitive and $G$-locally-quasiprimitive for some $G \leq \Aut(\Ga)$. In such a case we say that $\Ga \in \FB$ \emph{with respect to} $G$. } \end{definition} If one forms a quotient graph of a distance-transitive graph, with respect to a partition of the vertex-set which is invariant under the action of the given distance-transitive group, then the quotient graph is (``usually'') both distance-transitive and vertex-primitive. This is an over-simplification but it fairly accurately describes one of two combinatorial processes which are at the heart of the distance-transitive analysis. However, if one forms such quotients with a locally-quasiprimitive graph, then the quotient graph obtained is still arc-transitive, but in general is not locally-quasiprimitive. A fundamental observation about the class $\FB$ of finite locally-quasiprimitive, arc-transitive graphs is that it is closed under the formation of a very special type of quotient graph. \medskip \noindent\textbf{Some more notation:}\quad For ${\cal P}$ a partition of the vertex set $V$ of a graph $\Gamma$, we define the {\em quotient graph} $\Gamma_{\cal P}$ of $\Gamma$ relative to ${\cal P}$ as the graph with vertex set ${\cal P}$ such that two parts $P,P'$ form an edge if and only if there is at least one edge of $\Gamma$ joining a vertex of $P$ and a vertex of $P'$. If ${\cal P}$ is $G$-{\em invariant} for some group $G$ of automorphisms of $\Gamma$ (that is, $G$ permutes the parts of ${\cal P}$ setwise), then the action of $G$ on $\Gamma$ induces a natural action of $G$ as a group of automorphisms of $\Gamma_{\cal P}$. In this case, although the property of arc-transitivity is preserved, more restrictive local properties, such as local quasiprimitivity, are not in general inherited by the action of $G$ on the quotient graph. However, local quasiprimitivity is inherited by quotients relative to normal partitions. We call a partition ${\cal P}$ of vertices $G$-{\em normal relative to} $N$ if $N$ is a normal subgroup of $G$ and ${\cal P}$ is the set of $N$-orbits in $V$; for such partitions we write $\mathcal{P}=\mathcal{P}_N$, and we write the quotient graph $\Gamma_{\cal P}$ as $\Gamma_N$, and call $\Gamma_N$ a {\em normal quotient}, or a $G$-{\em normal quotient}, of $\Gamma$. Not only is $\Gamma_N$ \, a $G$-locally-quasiprimitive graph, but also $\Gamma$ is a multicover of $\Gamma_N$ and $N$ is semiregular on vertices. (A graph $\G$ is said to be a {\em multicover} of its quotient graph $\Gamma_{\cal P}$ if, for each edge $\{ P,P'\}$ of $\Gamma_{\cal P}$ and each $\alpha \in P$, the cardinality $|\Gamma(\alpha) \cap P'| >0$. A permutation group $N$ on a set $V$ is \emph{semiregular} on $V$ if the only element of $N$ which fixes a point of $V$ is the identity. If a group $G$ has an action on a set $V$ then $G^V$ denotes the permutation group induced by $G$ on $V$.) \begin{theorem}[{\cite[Section~1]{cep:p1}}] \label{thm:normal} Let $\G=(V,E)$ be a finite connected $G$-vertex-transit\-ive, $G$-locally-quasiprimitive graph of valency $v$, and let $N$ be a normal subgroup of $G$ with more than $2$ orbits on $V$. Then $\Ga_N=(\mathcal{P}_N,E_N)$ is a connected $G$-arc-transitive, $G$-locally-quasiprimitive graph of valency $v/k$ where, for each $\{P,P'\}\in E_N$ and each $\a\in P$, $|\Ga(\a)\cap P'|=k$, and $\Ga$ is a multicover of $\Ga_N$. Moreover, \begin{description} \item [(i)]$N$ is semiregular on $V$ and is the kernel of the action of $G$ on $\mathcal{P}_N$; \item[(ii)]if $P\in\mathcal{P}_N$ and $\a\in P$, then $G_{\a}^{\Ga(\a)}$ acts faithfully on the partition ${\cal P}(\a) :=\{\Ga(\a)\cap P'\, |\, \{ P,P'\}\in E_N\}$ of $\Ga(\a)$, and the permutation groups $G_{\a}^{\mathcal{P}(\a)}$ and $G_P^{\Ga_N(P)}$ are permutationally isomorphic; \item [(iii)] if moreover $\Ga$ is $G$-locally-primitive then $\Ga$ is a cover of $\Ga_N$ (that is $k=1$) and $\Ga_N$ is $G$-locally-primitive. \end{description} \end{theorem} The proof of this result may be found in \cite[Lemmas~1.1, 1.4(p), 1.5 and 1.6]{cep:p1}. Theorem~\ref{thm:normal} allows us to identify certain graphs in $\FB$ as `basic'. These are graphs for which the action of the group $G$ on vertices is `close' to being quasiprimitive. They are obtained by taking the normal subgroup $N$ in Theorem~\ref{thm:normal} to be maximal in some sense. We say that a group $G$ acting on a set $V$ is \emph{bi-quasiprimitive} if (i)\ $G$ is transitive on $V$, (ii)\ each normal subgroup of $G$ which acts non-trivially on $V$ has at most two orbits in $V$, and (iii)\ there exists a normal subgroup of $G$ with two orbits in $V$. A bi-quasiprimitive group $G$ on $V$ has a system of imprimitivity consisting of two blocks of size $|V|/2$, and hence has a subgroup $G^+$ of index 2 which fixes the two blocks setwise. Moreover, provided that $G\not\cong Z_2\times Z_2$ (acting regularly on a set of four points), then $G^+$ is the unique subgroup with these properties. A bipartite graph $\Ga=(V,E)$ is said to be $G$-\emph{bi-quasiprimitive} if $G$ acts as a group of automorphisms of $\Ga$ and $G$ is bi-quasiprimitive on $V$. \begin{theorem}[\cite{lpvz}] \label{thm:basic} Let $\Ga=(V,E)$ be a finite connected graph of valency $v$ which is $G$-vertex-transitive and $G$-locally-quasiprimitive, and let $N$ be a normal subgroup of $G$ which is maximal subject to having more than two orbits in $V$. Then one of the following holds for the quotient $\Ga_N$. \begin{description} \item [(a)] $\Ga_N$ is $G$-quasiprimitive; or \item [(b)] $\Ga$ and $\Ga_N$ are both bipartite, $N\le G^+$, and $\Ga_N$ is $G$-bi-quasiprimitive. Moreover, either $\Ga=K_{v,v}$, or $G^+$ acts faithfully on each part of the bipartition. \end{description} \end{theorem} We define a $G$-vertex-transitive, $G$-locally-quasiprimitive graph to be \emph{$G$-basic} if it is not a multicover of any of its proper $G$-normal quotients. By Theorem~\ref{thm:normal}, every graph in $\FB$ has at least one basic normal quotient, and by Theorem~\ref{thm:basic}, the basic graphs in $\FB$, apart from complete bipartite graphs, arise in three broad categories. \begin{corollary}[\cite{lpvz}]\label{cor:basic} Let $\Ga=(V,E)$ be a connected $G$-vertex-transitive, $G$-locally-quasi\-primit\-ive graph of valency $v$, and suppose that $\Ga$ is $G$-basic. Then either $\Ga=K_{v,v}$, or one of the following holds. \begin{description} \item[(a)]$\Ga$ is $G$-quasiprimitive; \item[(b)]$\Ga$ is bipartite, $G$-bi-quasiprimitive, and $G^+$ is faithful on each part of the bipartition. Moreover, either \begin{description} \item[(i)] $G^+$ is quasiprimitive on each part of the bipartition, or \item[(ii)] $G^+$ has distinct minimal normal subgroups, $M_1$ and $M_2$, which are semiregular on $V$ with more than two orbits in $V$, and are interchanged by $G$. \end{description} \end{description} \end{corollary} The class $\FB$ was first investigated in~\cite{cep:p2}. However it was not until 1993 that a systematic analysis was made of the structure of quasiprimitive permutation groups in \cite{cep}, enabling a detailed description of the structure of the quasiprimitive $2$-arc transitive graphs (an important subclass of $\FB$) to be made. In \cite{cep} an `O'Nan-Scott Theorem' for quasiprimitive groups, which described the possible structures of finite quasiprimitive permutation groups, was proved. Describing the bipartite members of $\FB$, or the bipartite $2$-arc transitive graphs, is not so easy, and is still an open problem. Complete bipartite graphs $K_{v,v}$ were singled out in~\cite[Lemma 1.1]{cep:p2}. These certainly arise as examples in Theorem~\ref{thm:basic}~(b) as can be seen by taking $G=S_v\wr S_2$. It would be interesting to ;;;;;; A natural problem arising from these results is the problem of constructing finite locally-quasiprimitive graphs as multicovers of a given locally-quasiprimitive graph. A universal construction method for such multicovers was given in \cite[Section 3]{lpvz}. It is a development of the covering graph construction of Biggs in~\cite{biggs}. \section{Imprimitive arc-transitive graphs} The class of finite arc-transitive graphs is so large that information about a vertex-primitive, arc-transitive quotient graph of a general arc-transitive graph $\G$ is unlikely to be sufficient to give a good understanding of the structure of $\G$. Something extra is required. The approach described here was first proposed in~\cite{Gardiner-Praeger95}. If $\G$ is a connected $G$-arc-transitive graph, and if $\mathcal{P}$ is a $G$-invariant partition of the vertex set, then the subset of vertices in a block $B$ of $\mathcal{P}$ is an independent set, that is, it contains no edges. It is possible, however, to define certain geometric objects based on the blocks of $\mathcal{P}$. For each vertex $\alpha$ of a $G$-arc-transitive graph $\Gamma$, we let $B(\alpha)$ denote the block of $\mathcal{P}$ containing $\alpha$. For a block $B \in \mathcal{P}$, we denote by $\Gamma(B)$ the set of vertices of $\Gamma$ adjacent to at least one vertex in $B$, and if $B, C$ are adjacent in $\G_\mathcal{P}$ we denote by $\Gamma[B, C]$ the induced bipartite subgraph of $\Gamma$ with $\Gamma (C) \cap B$ and $\Gamma (B) \cap C$ as the parts of the bipartition. Then $\Gamma[B, C]$ is $(G_{B \cup C})$-arc-transitive, where $G_{B \cup C}$ is the setwise stabilizer of $B \cup C$ in $G$. Up to isomorphism $\Gamma[B, C]$ is independent of the choice of adjacent blocks $B, C$. In particular, if $\Gamma[B, C]$ is a \emph{perfect matching} between the vertices of $B$ and $C$ (that is, each vertex of $B$ is joined to exactly one vertex of $C$, and vice versa), then $\Gamma$ is a {\em cover} of $\Gamma_{\mathcal{P}}$. In a similar way, for each block $B$, we denote by $\Gamma_{\mathcal{P}}(B)$ the set of blocks of $\mathcal{P}$ that are adjacent to $B$ in $\Gamma_{\mathcal{P}}$; and we define $\mathcal{D}(B)$ as the design with point set $B$ and blocks $\Gamma (C) \cap B$ (with possible repetitions) for $C \in \Gamma_{\mathcal{P}}(B)$. We emphasize that $\mathcal{D}(B)$ may have repeated blocks since we may have $\Gamma (C_1) \cap B = \Gamma (C_2) \cap B$ for distinct $C_1,C_2 \in \Gamma_{\mathcal{P}}(B)$. Set $k : = |\Gamma (B) \cap C|$ for adjacent blocks $B, C$ and $r : = |\Gamma_{\mathcal{P}}(\alpha)|$ for a vertex $\alpha$, where $\Gamma_{\mathcal{P}}(\alpha) := \{B \in {\mathcal{P}}: B \cap \Gamma(\alpha) \neq \emptyset\}$. Let $v : = |B|$ be the size of the blocks in $\mathcal{P}$ and $b : = {\rm val}(\Gamma_{\mathcal{P}}) = |\Gamma_{\mathcal{P}}(B)|$ be the valency of $\Gamma_{\mathcal{P}}$. Then $vr = bk$ and $\mathcal{D}(B)$ is a 1-$(v, k, r)$ design with $b$ blocks (see \cite{Biggs-White} for terminology on designs). Again, since $\Gamma$ is $G$-arc-transitive, the 1-design $\mathcal{D}(B)$ is, up to isomorphism, independent of the choice of the block $B$. It was suggested in \cite{Gardiner-Praeger95} that, in studying a $G$-arc-transitive graph $\Gamma$ with a nontrivial $G$-invariant partition $\mathcal{P}$ of the vertex set, the triple $(\Gamma_\mathcal{P}, \Gamma[B, C], \mathcal{D}(B))$ provides a useful collection of geometric structures for analysing the structure of $\Gamma$. The initial investigation in \cite{Gardiner-Praeger95} was extended in \cite{Gardiner-Praeger98, Gardiner-Praeger98a} to analyse arc-transitive graphs with complete quotients, and in \cite{lpz} to studying the special case ``$k=v-1$'' where the bipartite graph $\Gamma[B, C]$ involves most, but not necessarily all the vertices of $B\cup C$. These preliminary investigations suggest that this geometrical approach may be an effective way to gain insights into the structure of arc-transitive graphs. \section{Problems} Finally we state a few open problems, which were first given in \cite{lpvz}. The family ${\cal F}$ of finite graphs which admit a group acting transitively and locally-quasiprimitively on vertices deserves further study. First more detailed information about the basic locally-quasiprimitive graphs in ${\cal F}$ would be useful. \begin{problem} \label{prob:structure} Analyse further the structure of finite $G$-basic, $G$-arc-transitive, $G$-locally-quasiprimitive graphs. \end{problem} The most important tool currently available for this investigation is the `O'Nan-Scott' Theorem~\cite{cep} for finite quasiprimitive permutation groups. This can be used to analyse the non-bipartite $G$-basic graphs. Some work has commenced on this problem by Akshay Venkatesh and the author in the case where the group $G$ is of affine type. Much more detailed work has been undertaken already for the subfamily of non-bipartite $G$-basic graphs which are $(G,2)$-arc transitive, and a survey of these results is given in~\cite{bcc}. However we are lacking a similar group theoretic result for analysing the bipartite examples. \begin{problem} \label{prob:bi-quasiprimitive} Describe the finite bi-quasiprimitive permutation groups (in a manner similar to the O'Nan-Scott Theorem). Use this description to study bipartite $G$-basic, $G$-arc-transitive, $G$-locally-quasiprimitive graphs. \end{problem} The problem of reconstructing $\Gamma$ from information about all its basic normal quotient graphs $\Gamma_{N_i}$, ($i=1,\ldots,r$, say) remains open, and of fundamental importance. The maximum amount of information we could expect to retrieve about $\Gamma$ from these quotients would relate only to the graph $\Gamma_N$ where $N: = \cap_{i=1}^r N_i$. \begin{problem}\label{prob:rec} Suppose that $\Gamma$ is a finite graph which is $G$-vertex-transitive and $G$-locally-quasiprimitive, and that $\Gamma_{N_1},\ldots,\Gamma_{N_r}$ are quotients relative to normal subgroups $N_i$ of $G$ such that $\cap_{i=1}^r N_i = 1$. What extra information is needed in order to reconstruct $\Ga$ from these normal quotients? In particular, what is required if the graphs $\Ga_{N_i}$ are $G$-basic? \end{problem} A preliminary result was given in \cite{lpvz} for the case $r=2$. We need a more complete solution to Problem \ref{prob:rec} above, or to the following natural extension of it. \begin{problem} Suppose that $\Gamma$ is a finite graph which is $G$-vertex-transitive and $G$-local\-ly-quasiprim\-it\-ive, with $G$-normal quotient $\Gamma_N$. What extra information is needed to reconstruct $\Gamma$ from $\Gamma_N$? For example, under what circumstances is $\Gamma$ determined by $\Gamma_N$ together with the bipartite graph induced on the union of two adjacent $N$-orbits? \end{problem} Since quasiprimitivity is not necessarily inherited by overgroups, we need to address the following problem. \begin{problem} Under what circumstances can we guarantee that a graph $\Ga \in {\cal F}$ is $\mbox{\rm Aut}(\Ga)$-locally-quasiprimitive? In particular, when is this true for the basic graphs in ${\cal F}$? \end{problem} \begin{problem} Suppose $\Ga \in {\cal F}$ with respect to $G$, and $\Ga$ is $G$-basic. Under what circumstances is $\Ga$ also $\Aut(\Ga)$-basic? \end{problem} This problem has already received some attention in the case of 2-arc transitive graphs (see~\cite{li}) and almost simple locally-primitive graphs (see~\cite{fp, fhp}). Finally we note the following conjecture. \begin{conjecture} There is a function $f$ on the natural numbers such that, for a natural number $k$, if $\Gamma \in {\cal F}$ and $\Gamma$ has valency $k$, then the cardinality of a vertex stabilizer in $\mbox{\rm Aut}(\Gamma)$ is at most $f(k)$. \end{conjecture} This conjecture is analogous to one made by Weiss for finite locally-primitive graphs, and the task of proving Weiss's conjecture for non-bipartite graphs has been reduced in~\cite{clp} to proving it in the case where $\mbox{\rm Aut}(\Gamma)$ is an almost simple group (that is, $T \leq \mbox{\rm Aut}(\Gamma) \leq \mbox{\rm Aut} T$ for some nonabelian simple group $T$). Using the approach suggested here for describing graphs in ${\cal F}$, it may be possible to reduce the proofs of both this conjecture and the Weiss Conjecture to the case where $\mbox{\rm Aut}(\Gamma)$ is almost simple (whether or not the graphs are bipartite). Certainly one need only consider basic graphs $\Ga$, by Theorem~\ref{thm:basic}. \begin{thebibliography}{99} \bibitem{biggs} Norman Biggs, {\it Algebraic Graph Theory}, Cambridge University Press, Cambridge, (1993). \bibitem{Biggs-White} {\sc N.~L.~Biggs} and {\sc A.~T.~White}. {\em Permutation Groups and Combinatorial Structures}. London Math. Soc. Lect. Note Series No.~33 (Cambridge University Press, 1979). \bibitem{clp} M.~D.~Conder, Cai Heng Li and Cheryl E.~Praeger, On the Weiss conjecture for finite locally-primitive graphs, {\em Proc. Edinburgh Math. Soc.}, {\em submitted}. \bibitem{fp} Xin Gui Fang and Cheryl E.~Praeger, On graphs admitting arc-transitive actions of almost simple groups, {\em J.~Algebra} {\bf 205} (1998), 37--52. \bibitem{fhp} Xin Gui Fang, George Havas and Cheryl E.~Praeger, On the automorphism groups of quasiprimitive almost simple graphs, {\em submitted}. \bibitem{Gardiner-Praeger95} {\sc A.~Gardiner} and {\sc Cheryl E.~Praeger}. A geometrical approach to imprimitive graphs. {\em Proc. London Math. Soc.} (3){\bf 71}(1995), 524-546. \bibitem{Gardiner-Praeger98} {\sc A.~Gardiner} and {\sc Cheryl E.~Praeger}. Topological covers of complete graphs. {\em Math. Proc. Cambridge Phil. Soc.} {\bf 123}(1998), 549-559. \bibitem{Gardiner-Praeger98a} {\sc A.~Gardiner} and {\sc Cheryl E.~Praeger}. Symmetric graphs with complete quotients, {\em submitted}. \bibitem{ivanov} A.~A.~Ivanov, Distance-transitive graphs and their classification, in: {\it Investigations in the Algebraic Theory of Combinatorial Objects} (eds. I.A.Faradzev et al), Kluwer, Dordrecht (1994), pp.~283--378. \bibitem{li} Cai Heng Li, A family of quasiprimitive $2$-arc transitive graphs which have non-quasiprimitive full automorphism groups, {\em European J. Combin.} {\bf 19} (1998), 499--502. \bibitem{lpvz} Cai Heng Li, Cheryl E. Praeger, Alshay Venkatesh, and Sanming Zhou, Finite locally quasiprimitive graphs, preprint, 1998. \bibitem{lpz} Cai Heng Li, Cheryl E.~Praeger and Sanming Zhou, A class of finite symmetric graphs with 2-arc transitive quotients, {\em submitted}. \bibitem{cep:p1} Cheryl E.~Praeger, Imprimitive symmetric graphs, \emph{Ars Combinatoria} \textbf{19A} (1985), 149--163. \bibitem{cep:p2} Cheryl E.~Praeger, On automorphism groups of imprimitive symmetric graphs, \emph{Ars Combinatoria} \textbf{23A} (1987), 207--224. %labelled ``cep:p3" \bibitem{cep} Cheryl E.~Praeger, An O'Nan-Scott Theorem for finite quasiprimitive permutation groups and an application to 2-arc transitive graphs, {\it J. London Math. Soc. (2)} {\bf 47} (1993), 227--239. \bibitem{bcc} Cheryl E.~Praeger, Finite quasiprimitive graphs, in: {\it London Math. Soc. Lecture Note Ser.} {\bf 241}, Cambridge Univ.~Press, 1997, pp.~65--85. \bibitem{psy} Cheryl E.~Praeger, J.~Saxl and K.~Yokohama, Distance transitive graphs and finite simple groups, {\it Proc. London Math. Soc. (3)} {\bf 55} (1987), 1--21 . \bibitem{smith} D.~H.~Smith, Primitive and imprimitive graphs, {\it Quart. J. Math. Oxford (2)} {\bf 22} (1971), 551--557. \end{thebibliography} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%