\documentclass[12pt]{article} \usepackage{epsfig} %\documentstyle[12pt]{article} \setlength{\oddsidemargin}{0.2in} \newtheorem{thm}{Theorem} \newtheorem{lem}{Lemma} \newtheorem{cor}{Corollary} \newtheorem{prop}{Proposition} \newcommand{\ebox}{\hfill \rule{2.5mm}{2.5mm}\\\vspace{0.2cm}} \newcommand{\pr}{{\bf Proof.}\ } \newcommand{\bt}{\begin{thm}} \newcommand{\et}{\end{thm}} \newcommand{\bl}{\begin{lem}} \newcommand{\el}{\end{lem}} \newcommand{\bp}{\begin{prop}} \newcommand{\ep}{\end{prop}} \newcommand{\bc}{\begin{cor}} \newcommand{\ec}{\end{cor}} \newcommand{\be}{\begin{eqnarray}} \newcommand{\ee}{\end{eqnarray}} \newcommand{\bi}{\begin{itemize}} \newcommand{\ei}{\end{itemize}} \setlength{\textheight}{8.5in} \setlength{\textwidth}{6in} % hsize = 6in = 152mm % vsize = 9in = 229mm % primary font = 12pt. \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 5 (1998), \#R9\hfill} \thispagestyle{empty} \title{A note on constructing large Cayley graphs of given degree and diameter by voltage assignments\thanks{This research started when J. Plesn\' \i k and J. \v Sir\' a\v n were visiting the Department of Computer Science and Software Engineering of the University of Newcastle NSW Australia in 1995, supported by small ARC grant.}} \author{} \date{} \maketitle \begin{center} \vspace{-1.4cm} {\large Ljiljana Brankovi\' c, \ Mirka Miller} \\ {\small Department of Computer Science and Software Engineering, \\ The University of Newcastle NSW 2308 Australia,\\ e-mail: $\{$lbrankov,mirka$\}$@cs.newcastle.edu.au} \vspace{3mm} {\large J\'an Plesn\'{\i}k} \\ {\small Department of Numerical and Optimization Methods,\\ Faculty of Mathematics and Physics,\\ Comenius University, 842 15 Bratislava, Slovakia,\\ e-mail: plesnik@fmph.uniba.sk} \vspace{3mm} {\large Joe Ryan}\\ {\small Department of Mathematics, \\ The University of Newcastle NSW 2308 Australia, \\ e-mail: joe@frey.newcastle.edu.au} \vspace{3mm} {\large Jozef \v Sir\'a\v n} \\ {\small Department of Mathematics, \\ SvF Slovak Technical University \\ Radlinsk\' eho 11, 813 68 Bratislava, Slovakia, \\ e-mail: siran@lux.svf.stuba.sk} \vspace{3mm} Submitted: July 7, 1997; Accepted: August 8, 1997. \end{center} \begin{abstract} Voltage graphs are a powerful tool for constructing large graphs (called {\em lifts}) with prescribed properties as covering spaces of small {\em base} graphs. This makes them suitable for application to the {\em degree/diameter problem}, which is to determine the largest order of a graph with given degree and diameter. Many currently known largest graphs of degree $\le 15$ and diameter $\le 10$ have been found by computer search among Cayley graphs of semidirect products of cyclic groups. We show that {\em all} of them can in fact be described as lifts of smaller Cayley graphs of cyclic groups, with voltages in (other) cyclic groups. This opens up a new possible direction in the search for large vertex-transitive graphs of given degree and diameter. {\em AMS Subject Classification:} 05C25. \end{abstract} \section{Introduction} The problem of finding, for given $d$ and $k$, the largest order $n_{d,k}$ of a graph of maximum degree $d$ and diameter $\le k$ is well known as the {\em degree/diameter problem}. An obvious upper bound on $n_{d,k}$ is the {\em Moore bound} $M_{d,k}$, named after E. F. Moore who first proposed the problem (see~\cite{HoSi}): $n_{d,k}\le M_{d,k}=1+d+d(d-1)+\ldots +d(d-1)^{k-1}$. The equality $n_{d,k}=M_{d,k}$ holds only if {\it (a)} $k=1$ and $d\ge 1$, or {\it (b)} $k=2$ and $d=2,\ 3,\ 7$ (and, possibly, $d=57$), or {\it (c)} $k\ge 3$ and $d=2$; see \cite{HoSi,Dam,BaI1}. For all remaining values of $d$ and $k$ the best known general upper bound \cite{BaI2,ErFH} is $n_{d,k}\le M_{d,k}-2$, which was recently improved see~\cite{Jo} for trivalent graphs and $k\ge 4$ to $n_{3,k}\le M_{3,k}-4$. In the absence of better upper bounds a number of clever methods for constructing large graphs of given degree and diameter have been proposed. We just mention here various compounding operations~\cite{GoFS}, twisted product of graphs~\cite{BeDF}, polarity quotients~\cite{Del}, and linear congruential graphs~\cite{Opa2}; others are listed in \cite{Ha} and references therein. For computer search results we refer to~\cite{DiHa,Ha}. An updated list of currently largest known graphs of degree $d$ and diameter $k$ for $d\le 15$ and $k\le 10$ is maintained in~\cite{Delo}. For our purposes it is important to point out that, for $d\le k$, about a half of the values in the list have been obtained by searching over Cayley graphs of semidirect products of (mostly cyclic) groups. Actually, this fact has led to the introduction of the {\em vertex-transitive version} of the degree/diameter problem, which is finding the largest order $\nu_{d,k}$ of a vertex-transitive graph of degree $d$ and diameter $k$. Quite recently the current authors have argued~\cite{unlift} that the {\em covering graph construction} has a very good potential for producing examples of large graphs of given degree and diameter. Roughly speaking, this method enables to ``blow up'' a given {\em base graph} to a larger graph (called {\em lift}) which is a {\em regular covering space} of the base graph. The lift is best described in terms of the base graph and a mapping, called {\em voltage assignment}, which endows (directed) edges of the base graph with elements of a finite group. A self-contained introduction to the topic is provided in Section 2. As shown in \cite{unlift}, many of the currently known largest examples of graphs of given degree and diameter can indeed be obtained by the covering graph construction. Further, a recent result of~\cite{d2} which shows that $\nu_{d,2}\ge \frac89(d+\frac12)^2$ for all $d=(3q-1)/2$ such that $q=4\ell+1$ is a prime power was also obtained using voltage assignments. The objective of this paper is to show that, in fact, {\em all} the Cayley graphs of semidirect products of groups which appear in the tables of largest known graphs of given degree and diameter~\cite{DiHa,Ha,Delo} can be described as covering spaces of {\em smaller} base graphs, with voltage assignments taken in groups with a {\em simpler} structure; see Sections 4 and 5. (This of course does not exclude the possibility of finding -- by computer search or other methods -- even larger Cayley graphs based on groups which are not semidirect products.) We also include some observations on vertex-transitivity of a lift (Section 3). \section{Voltage assignments and lifts} Voltage assignments on graphs were formally introduced in 1974~\cite{Gross} as a dualisation of the {\em current graphs} theory, which was the basic tool in the proof of the famous Heawood Map Color Theorem~\cite{Ringel}. It turns out that (ordinary) voltage assignments on graphs are, in a sense, equivalent to semiregular groups of graph automorphisms (see Theorem 2.2.2 of \cite{GrTu}); since the latter were used in \cite{Frucht} for a concise description of certain graphs, this paper can also be seen as an ancestor for voltage graphs. The theory of voltage graphs and their lifts can be viewed as a discretization of the well known theory of {\em covering spaces} in algebraic topology applied to 1-dimensional cell complexes, i.e., graphs. (There are other viewpoints as well, known as theory of quotient graphs or divisors~\cite{CDS}, equitable partitions~\cite{Schwenk}, or colorations~\cite{Powers}.) The covering graph technique itself appears frequently as a tool in algebraic combinatorics; we may mention e.g., the computation of spectra of covering graphs \cite{CDS,Godsil}, the theory of distance-regular graphs \cite{Godsil}, a construction of infinitely many cubic 5-arc-transitive graphs \cite{Biggs}, or constructions of cages \cite{BiIto}. An excellent treatment of the theory of voltage graphs and their applications in constructing surface embeddings (including a voltage-based view of the Map Color Theorem) can be found in~\cite{GrTu}; for a more algebraic viewpoint see also Chapter 19 of \cite{Biggs}. In order to make this paper self-contained and accessible for readers not acquainted with the theory, we sum up the basics in what follows. Let $G$ be an undirected graph, which may have loops and/or parallel edges. We also allow $G$ to have semi-edges, that is, dangling edges with just one end incident to a vertex of $G$. (The occurence of the above three types of degeneracies may not be natural at a first glance but it is well accepted -- and sometimes unavoidable -- in algebraic graph theory.) Although the graph $G$ itself is undirected, it will be of advantage to assign (for auxiliary purposes) directions to its edges. An edge with an assigned direction will be called an {\em arc}. Clearly, each edge of $G$ which is not a semiedge gives rise to a pair of mutually {\em reverse} arcs. The reverse of an arc $e$ will be denoted $e^{-1}$; it is understood that $(e^{-1})^{-1}=e$. A semiedge will have, by definition, only one direction, outward of the incident vertex (which is considered to be both initial as well as terminal vertex of the semiedge). For convenience, if $e$ is an arc arising from a semiedge we still may formally use the symbol $e^{-1}$ but we set $e=e^{-1}$ in such a case. The collection of {\em all possible} arcs of $G$ will be denoted by $D(G)$. Let $\Gamma$ be a group and let $G$ be a graph. A mapping $\alpha:\ D(G)\to \Gamma$ will be called a {\em voltage assignment} on $G$ if, for each arc $e\in D(G)$, $\alpha (e^{-1})=(\alpha (e))^{-1} $. It follows that $(\alpha(e))^2=id$ if $e$ is an arc corresponding to a semiedge. In order to specify a voltage assignment in a pictorial representation of a graph, we usually fix in advance an orientation of the (undirected) graph $G$ and assign voltages to the arcs obtained; the reverse arcs are assumed to carry the corresponding inverse voltages. Let $\alpha : D(G)\to \Gamma$ be a voltage assignment on a graph $G$ in a group $\Gamma$. We now introduce the concept of a {\em lift} $G^{\alpha}$ of the graph $G$. The vertex set and the arc set of the lift are $V(G^{\alpha})=V(G)\times\Gamma$ and $D(G^{\alpha})=D(G)\times\Gamma$; we shall use subscripts for the $\Gamma$-coordinates of ordered pairs. The incidence in the lift is defined as follows. For any arc $e$ from $u$ to $v$ in $G$ and any $g\in\Gamma$ there is exactly one arc $e_g$ in the lift $G^{\alpha}$; this arc emanates from the vertex $u_g$ and terminates at the vertex $v_{g\alpha(e)}$. Observe that, in agreement with the definition, the arc $(e^{-1})_{g\alpha(e)}$ of the lift $G^{\alpha}$ emanates from $v_{g\alpha(e)}$ and terminates at $u_g$, because $\alpha(e^{-1})=(\alpha(e))^{-1}$. The pair of arcs $e_g$ and $(e^{-1})_{g\alpha(e)}$ constitutes an undirected {\em edge} of the lift $G^{\alpha}$; for the reverse arcs in the lift we therefore have $(e_g)^{-1}=(e^{-1})_{g\alpha(e)}$. Let $\pi :\ G^{\alpha}\to G$ be the {\em natural projection} which erases the subscripts, that is, $\pi (u_g)=u$ and $\pi (e_g)=e$ for each $u\in V(G)$, $e\in D(G)$ and $g\in \Gamma$. Clearly, $\pi$ is a graph homomorphism; the sets $\pi^{-1}(u)$ and $\pi^{-1}(e)$ are called {\em fibres} above the vertex $u$ or above the arc $e$, respectively. Thus, if $e$ is an arc from $u$ to $v$ and if $u\ne v$, then the arcs in $\pi^{-1}(e)$ constitute a matching between the fibres $\pi^{-1}(u)$ and $\pi^{-1}(v)$. If $e$ is a loop-arc at $u$ then the arcs in $\pi^{-1}(e)$ induce $|\Gamma|/k$ vertex-disjoint directed cycles on the set $\pi^{-1}(u)$ where $k$ is the order of $\alpha(e)$ in $\Gamma$. Finally, if $e$ is a semiedge-arc at $u$ then $\pi^{-1}(e)$ induces either a set of $|\Gamma|$ semiedges (if $\alpha(e)=id$) or a matching on $\pi^{-1}(u)$ (if $\alpha(e)$ has order two in $\Gamma$). Many properties of the lift can be identified by examining walks in the base graphs; examples will be given in Lemma 1 and in Theorem 1. We recall that a {\em walk} of length $m$ in a graph $G$ is a sequence $W=e_1e_2\ldots e_m$ where $e_i$ are {\em arcs} of $G$, such that the terminal vertex of $e_{i-1}$ is the same as the initial vertex of $e_i$, $2\le i\le m$. We say that $W$ is a $u-v$ walk if $u$ is the initial vertex of $e_1$ and $v$ is the terminal vertex of $e_m$. If $u=v$ then the walk $W$ is said to be {\em closed}, or {\em closed at} $u$. If $\alpha$ is a voltage assignment on $G$, then the {\em net voltage} of $W$ is defined as the product $\alpha (W)=\alpha (e_1)\alpha (e_2)\ldots \alpha(e_m)$. For a much more detailed exposition of the theory of voltage assignments and lifts we refer to~\cite{GrTu}. We conclude this Section by illustrating the concepts introduced above in the following useful observation (cf. \cite{unlift}). \bl \label{dist} Let $\alpha$ be a voltage assignment on a graph $G$ in a group $\Gamma$. Then, $diam(G^{\alpha})$\\ $\le k$ if and only if for each ordered pair of vertices $u,v$ (possibly, $u=v$) of $G$ and for each $g\in \Gamma$ there exists a $u-v$ walk of length $\le k$ of net voltage $g$. \el \pr For any two distinct vertices $u_g$ and $v_h$ in $V(G^{\alpha})$, there exists a walk $\tilde W$ of length at most $k$ from $u_g$ to $v_h$ if and only if the projection $W=\pi (\tilde W)$ is a walk in the base graph $G$ of length at most $k$ from $u$ to $v$ with $\alpha(W)=g^{-1}h$. (The case when both $u=v$ and $g=h$ follows by considering closed walks of zero length.)\hfill \rule{2.5mm}{2.5mm} \section{Lifts of graph automorphisms} In what follows we outline a method for finding voltage assignments which make the lift vertex-transitive (provided that the base graph is). First, observe that for any two vertices $u_g$ and $u_h$ in the same fibre $\pi^{-1}(u)$ there exists an automorphism of the lift which sends $u_g$ to $u_h$. Indeed, if $r=hg^{-1}$, the mapping $\tilde B_r:\ G^{\alpha}\to G ^{\alpha}$, given by $\tilde B_r(v_s)=v_{rs}$ for each $v_s\in V(G^{\alpha})$, is an automorphism of the lift $G^{\alpha}$ such that $\tilde B_r(u_g)=u_h$. Therefore, $Aut(G^{\alpha})$, the group of all automorphisms of $G^{\alpha}$, acts transitively on each fibre, and hence we always have $|Aut(G^{\alpha})|\ge |\Gamma |$. In fact, the insertion $r\mapsto \tilde B_r$ yields a {\em regular action} of the voltage group $\Gamma$ on the lift. In algebraic topology, lifts as introduced in Section 2 are called {\em regular covering spaces}; the adjective {\em regular} comes from the regular action described above. Further automorphisms of the lift may sometimes be obtained from automorphisms of the base graph. We say that an automorphism $A$ of $G$ {\em lifts} to an automorphism $\tilde A$ of $G^{\alpha}$ if $\pi \tilde A=A\pi$, that is, if $\pi (\tilde A(v_h))=A(\pi (v_h))$ for each vertex $v_h\in G^{\alpha}$. Note that $A(\pi (v_h))=A(v)$, and hence the lifted automorphism $\tilde A$ maps vertices from the fibre $\pi^{-1}(v)$ onto vertices in the fibre $\pi^{-1}(A(v))$; in other words, $\tilde A$ is {\em fibre-preserving}. Also, observe that if an automorphism $A\in Aut(G)$ lifts to some $\tilde A\in Aut(G^{\alpha})$, then $A$ has at least $|\Gamma|$ distinct lifts. This is due to the fact that for each $r\in \Gamma$, the composition $\tilde B_r\tilde A$ is a lift of $A$ as well, because $\pi \tilde B_r\tilde A=\pi \tilde A$. (Observe that the automorphisms $\tilde B_r$ themselves are lifts of the identity automorphism of $G$.) The following theorem was proved in \cite{GvSi} in a map-theoretical setting; for a graph-theoretical proof see \cite{RiSi}. \bt \label{autolift} Let $G$ be a connected graph, let $\alpha$ be a voltage assignment on $G$ in a finite group $\Gamma$, and let $A$ be an automorphism of $G$. Then, $A$ lifts to an automorphism of $G^{\alpha}$ if and only if for any closed walk $W$ at a fixed vertex of $G$ we have \ $ \alpha(W)=id \Leftrightarrow \alpha(A(W))=id$.\hfill \rule{2.5mm}{2.5mm} \et At a first glance, this result may seem not easily applicable, because it involves checking {\em all} closed walks. However, there is an easy way to reduce the checking to a number of walks proportional to the number of edges of $G$; see~\cite{RiSi} for details. Moreover, the structure of the base graph $G$ may sometimes be simple enough to check the above condition directly. An example of such a situation can be found in~\cite{d2} where vertex-transitivity of the lifts follows from Theorem~\ref{autolift} (although in~\cite{d2} a different method was used). Here we state and prove two useful corollaries of Theorem \ref{autolift} which we shall need later and where the amount of checking is reduced to a minimum. \bc \label{auto} Let $G$ be a connected graph and let ${\cal A}$ be a group of automorphisms of $G$. Let $\Gamma$ be a voltage group and let $\phi: {\cal A}\to Aut(\Gamma)$ be an arbitrary group homomorphism which sends each graph automorphism $A\in {\cal A}$ to an automorphism $\phi_A$ of the group $\Gamma$. Let $\alpha$ be a voltage assignment on $G$ in the group $\Gamma$ such that $\alpha(A(e))=\phi_A(\alpha(e))$ for each arc $e\in D(G)$. Then each automorphism $A\in {\cal A}$ lifts to an automorphism of $G^{\alpha}$. \ec \pr Let $W=e_1e_2\ldots e_k$ be a walk in $G$. Consider its image $A(W)=A(e_1)A(e_2)$\\ $\ldots A(e_k)$ under a graph automorphism $A\in {\cal A}$. Due to the fact that $\phi_A$ is an automorphism of the group $\Gamma$, we have $\alpha(A(W))=\prod_{i=1}^k\alpha(A(e_i))=\prod_{i=1}^k\phi_A(\alpha(e_i)) =\phi_A(\prod_{i=1}^k\alpha(e_i))=\phi_A(\alpha(W))$. It follows that $\alpha(W)=id$ if and only if $\alpha(A(W))=id$; note that in this case we obtained the equivalence for {\em all} walks, not only for the closed ones. The rest follows from Theorem~\ref{autolift}. \hfill \rule{2.5mm}{2.5mm} \bc \label{cycauto} Let $A$ be an automorphism of order $k$ of a graph $G$. Let $\alpha$ be a voltage assignment on $G$ in the additive group ${\cal Z}_n$. Assume that there is an element $b$ in ${\cal Z}_n$ of multiplicative order $k$, which has a multiplicative inverse in the ring $({\cal Z}_n,+,.)$ and such that $\alpha (A(e))=b\alpha (e)$ for each arc $e\in D(G)$. Then $A$ lifts to an automorphism of $G^{\alpha}$. \ec \pr Let ${\cal C}_A$ be the cyclic group of order $k$ generated by the automorphism $A$. Then we have an obvious homomorphism $\phi:\ {\cal C}_A\to Aut({\cal Z}_n,+)$, given by $\phi_A(r)=br$ for each $r\in ({\cal Z}_n,+)$. The claim now follows from Corollary~\ref{auto}. \hfill \rule{2.5mm}{2.5mm} \section{Lifts of Cayley graphs and semidirect products} Let $\Lambda$ be a group and let $X=(x_1,x_2,\ldots ,x_d)$ be a generating {\em sequence} of $\Lambda$ for which there exists an involution $\tau$ on the set $\{1,2,\ldots ,d\}$ such that $x_{\tau(i)}=x_i^{-1}$ for $1\le i\le d$. The {\em Cayley graph} $H=Cay(\Lambda,X)$ has vertex set $V(H)=\Lambda$ and arc set $D(H) =\{(b,i);\ b\in \Lambda ,\ 1\le i\le d\}$. For each vertex $b$ and each $i$, $1\le i\le d$, the arc $(b,i)$ emanates from $b$ and terminates at the vertex $bx_i$. Since, by the same token, the arc $(bx_i,\tau(i))$ emanates from $bx_i$ and terminates at $b$, the two arcs are considered mutually reverse; in symbols, $(b,i)^{-1}=(bx_i,\tau(i))$. In other words, the pair $\{(b,i), (bx_i,\tau(i))\}$ constitutes an undirected edge. The resulting Cayley graph is therefore {\em undirected}; it is clearly connected and regular of degree $d$.. For each $a\in \Lambda$, the left multiplication $A_a:\ b\mapsto ab$ is an automorphism of the Cayley graph $H=Cay(\Lambda,X)$, which explicitly shows that Cayley graphs are vertex-transitive. The collection ${\cal A}_{\Lambda}=\{A_a;\ a\in\Lambda\}$ is a group isomorphic to $\Lambda$. It is important to clarify how repeated generators and/or the unit element of the group in the generating sequence $X$ correspond to parallel edges, loops, and semiedges in our Cayley graphs. Whenever $x_i=x_j$ for some $i\ne j$, from each vertex $b$ we have a pair of parallel arcs $(b,i)$ and $(b,j)$. If $x_i=id$ and $i\ne \tau(i)$, we have a loop $(b,i)$ at each vertex $b$; combined with the preceding condition we may have parallel loops as well. Finally, if $x_i=id$ and $i=\tau(i)$ then $(b,i)$ represents a semiedge at $b$. Let $\alpha:\ D(H)\to \Gamma$ be a voltage assignment on a Cayley graph $H=Cay(\Lambda,X)$. We say that $\alpha$ satisfies the {\em compatibility condition} if there exists a group homomorphism $\phi:\ \Lambda\to Aut(\Gamma)$ which sends an element $a\in \Lambda$ to an automorphism $\phi_a$ of $\Gamma$, such that \be \label{1} \alpha(a,i)=\phi_a(\alpha(id,i)) \ee for each arc $(a,i)$ of $H$. Clearly, if a voltage assignment $\alpha$ satisfies the compatibility condition, then $\alpha$ is completely determined by the distribution of voltages on the arcs emanating from the vertex $id\in \Lambda$. The advantage of having such voltage assignment is obvious from the next consequence of Corollary~\ref{auto}. Before stating the result we need to introduce one more concept. A voltage assignment $\alpha$ on a connected graph $G$ will be called {\em proper} if the lift $G^{\alpha}$ is connected. (For an easy necessary and sufficient condition for a voltage assignment to be proper we refer to~\cite{GrTu}.) \bt \label{Sabid} Let $H=Cay(\Lambda,X)$ be a Cayley graph and let $\alpha$ be a proper voltage assignment on $H$ in a group $\Gamma$ which satisfies the compatibility condition. Then, the lift $H^{\alpha}$ is a Cayley graph. \et \pr As before, let ${\cal A}_{\Lambda}\simeq \Lambda$ be the subgroup of $Aut(H)$ induced by left multiplication by elements of $\Lambda$. Let $\phi$ be the homomorphism associated with the compatibility condition; it is easy to show that (\ref{1}) actually implies $\alpha(ab,i)=\phi_a(\alpha(b,i))$ for any $a,b\in\Lambda$ and $x_i$ in $X$. Invoking this identity in concert with Corollary~\ref{auto}, we see that each automorphism in the group ${\cal A}_{\Lambda}$ lifts to an automorphism of $H^{\alpha}$. Let $\tilde {\cal A}_{\Lambda}$ denote the collection of all such lifts; it is an easy exercise to show that $\tilde{\cal A}_{\Lambda}$ is a {\em group}. Since each automorphism of ${\cal A}_{\Lambda}$ lifts to $|\Gamma|$ distinct automorphisms of $\tilde{\cal A}_{\Lambda}$ and no two of them are equal, we have $|\tilde{\cal A}_{\Lambda}|=|V(H^{\alpha})|$. A straightforward inspection shows that the lifted group $\tilde {\cal A}_{\Lambda}$ acts transitively (and, due to the above counting, regularly) on the vertex set of the lift. By a classical theorem of Sabidussi~\cite{Sab}, the lift $H^{\alpha}$ is a Cayley graph (for the group $\tilde{\cal A}_{\Lambda}$). \ebox Knowing that a lift is a Cayley graph, it is natural to ask about the structure of the underlying group of the lift. A general theory on covering Cayley graphs with Cayley graphs is outlined in~\cite{RiSi}. Here we just consider the special case referred to in Theorem~\ref{Sabid}. For that reason we recall the concept of {\em semidirect product} $\Lambda\times_{\phi}\Gamma$ of the groups $\Lambda$ and $\Gamma$ (which depends on the above homomorphism $\phi:\ \Lambda\to Aut(\Gamma)$) where the multiplication of elements $(a,g),(b,h)\in\Lambda\times\Gamma$ is given by $(a,g)(b,h)=(ab,g\phi_a(h))$. \bt \label{semi} Let $H=Cay(\Lambda, X)$ be a Cayley graph and let $\phi:\Lambda\to Aut(\Gamma)$ be a group homomorphism. (i) \ Let $\alpha$ be a proper voltage assignment on $H$ in $\Gamma$ satisfying (\ref{1}). Then the lift $H^{\alpha}$ is isomorphic to the Cayley graph $Cay(\Lambda\times_{\phi}\Gamma,X^{\alpha})$, with generating sequence $X^{\alpha}=(x_1,\alpha(id,1)),(x_2,\alpha(id,2)),\ldots , (x_d,(\alpha(id,d))$. (ii) \ Conversely, let $Cay(\Lambda\times _{\phi}\Gamma, Y)$ be a Cayley graph for the semidirect product $\Lambda\times_{\phi}\Gamma$ with a generating sequence $Y=((x_1,y_1),(x_2,y_2),\ldots ,(x_d,y_d))$. Then there exists a Cayley graph $H=Cay(\Lambda,X)$ and a voltage assignment $\alpha$ on $G$ satisfying (\ref{1}), such that $H^{\alpha}\simeq Cay(\Lambda\times_{\phi}\Gamma, Y)$. Explicitly, $X=(x_1,x_2,\ldots ,x_d)$ and $\alpha(a,i)=\phi_a(y_i)$. \et \pr (i) \ Let the generating sequence $X$ have $d$ terms. By the definition of a lift, for $1\le i\le d$ there is an arc in $H^{\alpha}$ from $(a,g)$ to $(b,h)$ with ``label'' $i$ if and only if $ax_i=b$ for $x_i$ in $X$ and, at the same time, $h=g\alpha (a,i)= g\phi_a(\alpha(id,i))$. But this adjacency condition is equivalent to the following multiplicative property in the semidirect product $\Lambda\times_{\phi}\Gamma$: \[ (a,g)(x_i,\alpha(id,i))=(ax_i,g\phi_a(\alpha(id,i)))=(b,h)\ \] which actually defines the Cayley graph $Cay(\Lambda\times_{\phi}\Gamma, X^{\alpha})$. (ii) \ Let $Y=((x_1,y_1),(x_2,y_2),\ldots ,(x_d,y_d))$ be the generating sequence for the semidirect product. Then $X=(x_1,x_2,\ldots ,x_d)$ is a generating sequence for the group $\Lambda$. For each arc $(a,i)$ of the Cayley graph $Cay(\Lambda,X)$ define the voltage assignment $\alpha$ by $\alpha(a,i)=\phi_a(y_i)\in \Gamma$. The verification of the isomorphism $H^{\alpha}\simeq Cay(\Lambda\times_{\phi}\Gamma, Y)$ is straightforward. \hfill \rule{2.5mm}{2.5mm} \section{Application} The 1--1 correspondence in Theorem \ref{semi} opens up a new direction in a possible search for large vertex-transitive graphs of given degree and diameter. As mentioned earlier~\cite{Ha}, a large number of the currently known record examples were found among Cayley graphs of semidirect products of cyclic groups. Our Theorem~\ref{semi} shows how to reconstruct each such Cayley graph in terms of a lift of a {\em smaller} Cayley graph of a {\em cyclic} group, with voltages taken in some smaller {\em cyclic} group as well. This strongly suggests that a computer search over lifts of small graphs (not necessarily Cayley) using various voltage assignments (not necessarily satisfying the compatibility condition in case of Cayley graphs) may lead to further new examples of large graphs of given diameter and degree. Lemma 1 may then serve as a tool for testing the diameter of the lift. We shall now illustrate the above facts on one of the current record graphs. \vskip 3mm \noindent {\bf Example}. The largest known vertex-transitive graph of degree 9 and diameter 4, which has 1430 vertices, was found \cite{DiHa} as the Cayley graph $G=Cay({\cal Z}_{10}\times_{\phi} {\cal Z}_{143},Y)$. The homomorphism $\phi:\ {\cal Z}_{10}\to Aut({\cal Z}_{143})$ is given by $\phi_a (j)=64^aj$, $a=0,1,2,\ldots ,8,9$ (multiplication in the {\em ring} $({\cal Z}_{143},+,.)$) and $Y=((0,59), (0,84), (1,51), (3,80), (3,121),$\\ $ (5,0),$ $(7,54), (7,121), (9,64))$. (We note that in~\cite{DiHa,Ha} this semidirect product is denoted by the symbol $10\times_{64}143$, and the exposition there is based on a different but algebraically equivalent description of semidirect products.) By Theorem~\ref{semi}, the graph $G$ is isomorphic to the lift of a Cayley graph $H=Cay({\cal Z}_{10},X)$ whose structure is easily determined. For the generating sequence $X=(x_1,x_2,\ldots,x_9)$ we have $x_1=x_2=0$, $x_3=1$, $x_4=x_5=3$, $x_6=5$, $x_7=x_8=7$, and $x_9=9$; the corresponding involution $\tau$ is given by $\tau(1)=2$, $\tau(3)=9$, $\tau(4)=7$, $\tau(5)=8$, and $\tau(6)=6$. Note that $H$ has, at each vertex, one loop and two pairs of parallel edges (see Fig. \ref{10}). For brevity, let $\alpha_i$ denote the voltage of the arc $(id,i)=(0,i)$ of $H$, $1\le i\le 9$, in the group ${\cal Z}_{143}$. Then, following the part {\em (ii)} of Theorem~\ref{semi} we have $\alpha_1=59$, $\alpha_2=84$, $\alpha_3=51$, $\alpha_4=80$, $\alpha_5=121$, $\alpha_6=0$, $\alpha_7=54$, $\alpha_8=121$, and $\alpha_9=64$. In accordance with the compatibility condition (\ref{1}) the voltage assignment extends to the remaining arcs of $H$ by setting $\alpha(a,i)=\phi_a(\alpha(0,i))=\phi_a(\alpha_i)=64^a\alpha_i$. As we see, using a suitable voltage assignment in the cyclic group of order 143, the graph $G$ of order $1430$ can be obtained by ``blowing up'' a comparatively very small graph -- of order 10 only! %\newpage \begin{figure}[ht] \centerline{\hbox{ \psfig{figure=10.eps,height=3.5in,width=3.5in}}} \caption{A local view of the base Cayley graph $H=Cay({\cal Z}_{10},X)$ for the graph $G=10\times_{64}143$; the rest of the graph is obtained by rotation. The values in brackets are voltages (in ${\cal Z}_{143}$) on the arcs $(0,i)$ corresponding to the generators $x_i$. The voltages on the remaining arcs $(a,i)$ are given by $\alpha(a,i)=\phi_a(\alpha(0,i))$. \label{10}} \end{figure} \begin{thebibliography}{xxxx} \bibitem{BaI1} E. Bannai, T. Ito, On finite Moore graphs, {\em J. Fac. Sci. Tokyo Univ.} {\bf 20} (1973) 191-208. \bibitem{BaI2} E. Bannai, T. Ito, Regular graphs with excess one, {\em Discrete Math.} {\bf 37} (1981) 147-158. \bibitem{BeDF} J.-C. Bermond, C. Delorme, G. Farhi, Large graphs with given degree and diameter, {\em J. Combin. Theory Ser. B} {\bf 36} (1984) 32-48. \bibitem{Biggs} N. L. Biggs, ``Algebraic Graph Theory'', Cambridge Univ. Press (2nd Edition), 1993. \bibitem{BiIto} N. L. Biggs, T. Ito, Graphs with even girth and small excess, {\em Math. Proc. Cambridge Philos. Soc.} {\bf 88} (1980) 1-10. \bibitem{unlift} L. Brankovi\'c, M. Miller, J. Plesn\'\i k, J. Ryan, J. \v Sir\'a\v n, Large graphs with small degree and diameter: A voltage assignment approach, {\em submitted}. \bibitem{CDS} D. M. Cvetkovi\'c, M. Doob, H. Sachs, ``Spectra of Graphs'', Barth Verlag, Heidelberg, 1995. \bibitem{Dam} R. M. Damerell, on Moore graphs, {\em Proc. Cambridge Philos. Soc.} {\bf 74} (1973) 227-236. \bibitem{Del} C. Delorme, Examples of products giving large graphs with given degree and diameter, {\em Discrete Applied Math.} {\bf 37/38} (1992) 157-167. \bibitem{Delo} C. Delorme, A table of largest $(\Delta,D)$-graphs, available at the e-mail address `` Charles.Delorme@lri.fr'' upon request. \bibitem{DiHa} M. J. Dineen, P. R. Hafner, New results for the degree/diameter problem, {\em Networks} {\bf 24} (1994) 359-367. \bibitem{ErFH} P. Erd\H os, S. Fajtlowicz, A. J. Hoffman, Maximum degree in graphs of diameter 2, {\em Networks} {\bf 10} (1980) 87-90. \bibitem{Frucht} R. W. Frucht, How to describe a graph, in: Int. Conf. Combin. Math., {\em Ann. N. Y. Acad. Sci.} {\bf 175} (1970) 159-167. \bibitem{Godsil} C. D. Godsil, ``Algebraic Combinatorics'', Chapman and Hall, 1993. \bibitem{GoFS} J. G\'omez, M. A. Fiol, O Serra, On large $(\Delta,D)$-graphs, {\em Discrete Mathematics} \bibitem{Gross} J. L. Gross, Voltage graphs, {\em Discrete Math.} {\bf 9} (1974) 239-246. \bibitem{GrTu} J. L. Gross and T. W. Tucker, {\em Topological Graph Theory}, Wiley, New York (1987). \bibitem{GvSi} P. Gvozdjak and J. \v Sir\'a\v n, Regular maps from voltage assignments, {\em Graph Structure Theory} (Contemporary Mathematics AMS Series) {\bf 147} (1993) 441-454. \bibitem{Ha} P. R. Hafner, Large Cayley graphs and digraphs with small degree and diameter, {\em Computational Algebra and Number Theory} (W. Bosma and van der Poorten, Eds.) Kluwer, Amsterdam (1995) 291-302. \bibitem{HoSi} A. J. Hoffman, R. R. Singleton, On Moore graphs with diameter 2 and 3, {\em IBM J. Res. Develop.} {\bf 4} (1960) 497-504. \bibitem{Jo} L. K. Jorgensen, Diameters of cubic graphs, {\em Discrete Applied Math.} {\bf 37/38} (1992) 347-351. \bibitem{d2} B. D. McKay, M. Miller, J. \v Sir\'a\v n, A note on large graphs of diameter two and given maximum degree, {\em submitted}. \bibitem{Opa2} J. Opatrn\'y, D. Sotteau, N. Srinivasan, K. Thulasiraman, DCC Linear Congruential Graphs: A new Class of Interconnection Networks, {\em IEEE Transactions on Computers,} {\bf 45} No. 2 (1996). \bibitem{Powers} D. L. Powers, M. M. Sulaiman, The walk partition and coloration of a graph, {\em Linear Algebra Appl.} {\bf 48} (1982) 145-159. \bibitem{RiSi} R. B. Richter, J. \v Sir\'a\v n, Covering Cayley graphs with Cayley graphs, preprint (1996). \bibitem{Ringel} G. Ringel, ``Map Color Theorem'', Springer, 1974. \bibitem{Sab} G. Sabidussi, On a class of fixed-point free graphs, {\em Proc. Amer. Math. Soc.} {\bf 9} (1958) 800-804. \bibitem{Schwenk} A. J. Schwenk, Computing the characteristic polynomial of a graph, in: ``Graphs and Combinatorics'', {\em Lect. Notes in Math.} {\bf 406} (Springar, Berlin, 1974), 153-162. %\bibitem{Sta} R. G. Stanton, S. T. E. Seah, D. D. Cowan, Nonexistence of %an extremal graph of a certain type, {\em J. Austral. Math. Soc. (A)} %{\bf 30} (1980) 55-64. \end{thebibliography} \end{document}