Sari

Catatan untuk keberadaan graf berarah hampir Moore derajat 3

Telah lama diketahui bahwa tidak ada graf berarah dengan orde (jumlah titiknya) sama dengan batas Moore, kecuali untuk kasus-kasus trivial, yakni untuk derajat 1 atau diameter 1; tetapi, ada graf berarah dengan diameter 2 untuk sebarang derajat dengan orde satu lebih kecil dari batas Moore. Hingga kini belum dapat ditunjukkan adanya contoh graf berarah yang sejenis dengan diameter paling sedikit 3, walaupun beberapa syarat perlu akan keberadaannya telah diberikan. Salah satu syarat perlu yang cukup menarik untuk keberadaan graf berarah dengan derajat 3, diameter \(k \ge 3\) dan orde satu lebih kecil dari batas Moore adalah bahwa jumlah busur yang dimilikinya harus dapat dibagi oleh bilangan k + 1.

Dalam tulisan ini, kami akan menurunkan syarat perlu lain yang berkaitan dengan permutasi perulangan yang harus dimilikinya. Sebagai konsekuensi, kami dapat menunjukkan bahwa graf berarah tersebut (bila ada) bukan merupakan graf berarah Cayley dari suatu grup komutatif.

Kata kunci: Graf berarah hampir Moore, masalah derajat/diameter, pemetaan voltase, grah berarah Cayley.

1 Introduction and preliminaries

The well known degree/diameter problem for digraphs is to determine the largest order \(n_{d,k}\) of a digraph of (out)degree at most d and diameter at most k. A straightforward upper bound on \(n_{d,k}\) is the Moore bound \(M_{d,k}\):

\[n_{d,k} \le M_{d,k} \le 1 + d + d^2 + ... + d^k\]

It is well known that \(n_{d,k} = M_{d,k}\) only in the trivial cases when d=1 (directed cycles of length k+1) or k=1 (complete digraphs of order d+1), see [12] or [7]. For k=2, line digraphs of complete digraphs are examples showing that \(n_{d,2} = M_{d,2} - 1\) if \(d \ge 2\). On the other hand, if d=2 then \(n_{2,k} < M_{2,k} - 1\) for \(k \ge 3\) (see [11]). Moreover, from the necessary conditions obtained in

[10] it follows that, for example, \(n_{2,k} < M_{2,k} - 2\) for \(3 \le k \le 10^7\), \(k \ne 274485\), 5035921. The question of whether or not equality can hold in \(n_{d,k} \le M_{d,k} - 1\) for \(d \ge 3\) and \(k \ge 3\) is completely open.

For convenience, a digraph of (out) degree at most d, diameter at most k (where \(d \ge 3\) and \(k \ge 2\)) and order \(M_{d,k}-1\) will be called a (d,k)-digraph. It is an easy exercise to show that a (d,k)-digraph must be diregular of degree d (the in-degree and out-degree of each vertex are exactly d), and its diameter must be equal to k.

Several necessary conditions for the existence of (d,k)-digraphs have been proved in [2–6]. In particular, for d = 3 it was proved in [3] that (3,k)-digraphs do not exist if k is odd or if k + 1 does not divide \(\frac{9}{2}(3k - 1)\). All these conditions refer in one way or another to the socalled repeats which were first introduced in [11] and which we recall next.

Let G be a (d,k)-digraph. A simple counting argument shows that for each vertex u of G there exists exactly one vertex r(u) in G with the property that there are two \(u \to r(u)\) walks in G of length not exceeding k. The vertex r(u) is called the repeat of u. It can be shown [3] that the mapping \(v \to r(v)\) is an automorphism of G. In what follows we shall therefore refer to r as the repeat automorphism of the (d,k)-digraph G.

Very recently, for d = 3 it has been proved in [6] that all cycles of the repeat automorphism r (when written as a permutation of the vertex set of a (3,k)-digraph) must have the same length. However, cycles of length one are impossible, due to an earlier result of [3] which says that for \(k \ge 3\) and \(d \ge 2\) there is no (d,k)-digraph for which r is an identity automorphism.

The purpose of this note is to examine the other extreme; we show that the cycles of a repeat automorphism of a (d,k)-digraph cannot be too long (Section 4, Theorem 1). As a consequence of our method we shall prove that a (d,k)-digraph cannot be a Cayley graph of an Abelian group. We use an algebraic approach to the problem; the basics are introduced in Sections 2 and 3.

2 Algebraic background

Let G be a digraph and let I' be a subgroup of Aut(G), the group of all automorphisms of G, viewed as a group of permutations of the vertex set V(G). In addition, let us assume that \(\Gamma\) is semi-regular on V(G), that is, for any ordered pair of vertices \(u, v \in V(G)\) (possibly u = v) there exists at most one automorphism \(g \in \Gamma\) such that g(u) =v. Then we may define the quotient digraph \(G/\Gamma\) as follows. The vertex set \(V(G/\Gamma)\) is the set of all orbits \(O(u) = \{g(u); g \in \Gamma\}\) of the group \(\Gamma\) on V(G). If O(u), O(v) is any ordered pair of vertices of the quotient digraph \(G/\Gamma\) (that is, any pair of orbits of \(\Gamma\) on V(G); we do not exclude the case O(u) = O(v) and if in the original digraph G there are t arcs emanating from u and terminating in O(v), then there will be t parallel arcs in \(G/\Gamma\) emanating from O(u) and terminating at O(v). Note that in the case when O(u) = O(v) the t arcs will become t loops attached at the vertex O(u). The fact that quotient digraphs are well defined (i.e., incidence in the quotient graph does not depend on the choice of a particular vertex in the orbit) is an easy consequence of semi-regularity of \(\Gamma\) on V(G). It is more important to notice that the projection \(\rho\): \(V(G) \to V(G/\Gamma)\) given by \(\rho(u) = O(u)\) is a digraph epimorphism.

Note that if, in the situation above, the group \(\Gamma\) is regular on V(G) – that is, if for any ordered pair \((u,v) \in V(G) \times V(G)\) there exists exactly one automorphism \(g \in \Gamma\) such that g(u) = v – then G is isomorphic to a Cayley digraph for the group \(\Gamma\) and the quotient digraph \(G/\Gamma\) consists of a single vertex only (with d loops attached to it if G is d-regular).

We shall soon be facing the following converse problem: Given a digraph H, what are the possible digraphs G and semi-regular subgroups \(\Gamma \leq Aut(G)\) for which the quotient digraph \(G/\Gamma\) is isomorphic to H? A complete answer can be given in terms of the so-called voltage assignments and lifts. Voltage assignments on (undirected) graphs were introduced in the early 70's [8] as a dual form of current graphs; the latter played a key role in proving the famous Map Color Theorem. Most of the theory (summarised in [9]) can be immediately transferred to digraphs, and in what follows we outline only the basic facts.

Let H be a digraph, possibly containing directed loops and/or parallel arcs. Let \(\Gamma\) be an arbitrary group. Any mapping \(\alpha: D(H) \to \Gamma\) is called a voltage assignment on H. The lift of H by \(\alpha\), denoted by \(H^{\alpha}\), is the digraph defined as follows: \(V(H^{\alpha}) = V(H) \times \Gamma\), \(D(H^{\alpha}) = D(H) \times \Gamma\), and there is an arc (x,f) in \(H^{\alpha}\) from (u,g) to (v,h) if and only if f = g, x is an arc from u to v, and \(h = g\alpha(x)\). The mapping \(\pi: H^{\alpha} \to H\) which erases the second coordinates, that is, \(\pi(u,g) = u\) and \(\pi(x,g) = x\) for each \(u \in V(H)\), \(x \in D(H)\) and \(g \in \Gamma\), is called a natural projection. Clearly, \(\pi\) is a digraph epimorphism; the sets \(\pi^{-1}(u)\) and \(\pi^{-1}(x)\) are called fibres above the vertex u or above the arc x, respectively.

For any two vertices in the same fibre \(\pi^{-1}(u)\) there exists an automorphism of the lift which sends the first vertex to the second. Indeed, without loss of generality, let \((u,id),(u,g) \in \pi^{-1}(u)\) be a pair of such vertices. Then it can be easily checked that the mapping \(B_g: H^{\alpha} \to H^{\alpha}\), given by \(B_g(v,h) = (v,gh)\) for each \((v,h) \in V(H^{\alpha})\), is an automorphism of the lift \(H^{\alpha}\) such that \(B_g(u,id) = (u,g)\). Observe that the collection \(\widetilde{\Gamma} = \{B_g; g \in \Gamma\}\) forms a semi-regular subgroup (isomorphic to \(\Gamma\)) of the group \(Aut(H^{\alpha})\); the fibres coincide with the orbits of \(\widetilde{\Gamma}\).

A close connection between quotients and lifts may already be apparent from the definitions. Indeed, the basic result on semi-regular group actions on undirected graphs, which is Theorem 2.2.2 of [9], immediately translates to the following directed version:

Proposition 1 Let G be a digraph and let \(\Gamma < Aut(G)\) be a semi-regular subgroup on V(G). Then there exists a voltage assignntent a on the quotient digraph Glf in lhe groupl such that the lift (G/f)'is isornorphic toG.

Thus, for a given quotient digraplt FI, all possible digraphs G (and semi-regular groups fon I(G)) can bc re-constructed by considering voltage assigntnents on the digraph .I/ and the corresponding lifts.

3 The diameter of a lift

We shall also be interested in recovering sorne properties of a lift from propertics of the quotient. For this purpose we outline the connection betl'een closcd walks in the quotient and in the lift. Let cr be a voliage assignrnent on a digraph I/ in a group f . Lct IV = xrx:. . . x.be a walk in H, i.e., an arc sequence in u4rich the terminal veftex of x;-1 coincides rvith the initial vertex of x; for each i,2 < i < rr (rve allorv an arc to bc used repeatedly). The nurnber n is the length of the u'alk ltrl. The walk IV is closed if the initial vertex of x1 and the terminal vertex of r. coincide. The net voltage of IIi is sirnply the product aln = a(x1)a(r2)... a(x-). For convenience, at each vertex we also admit a triviol closed walk oflenglh 0 and ofunit net voltage.

It is easy to see that for eaclt s,alk Itrl = xrx:. .. x. in I{ from a vertex il to vertex v and for each g e f there exists a unique walk fr in the lift .Ff emanating from the vertex (r,g) and such that n(V '1= Itrl. This walk has the form 17 - (r1.g)(x2.ga(x1))... (x..gcr(x1) cr(x:). o(r.-r)); it emanates in the lift from the vcrtex (u,g) and terminates at the vertex (v,gcl;(lI)). The rvalk 17 is often called a lift of IV.

Note tlrat for an1, trl'o distinct verticcs (u,g),(,,h) in V(If) tltere exists a path I7 of length at most fr frorn (ug) to (v,fi) if and only if the projection II/ = n(t7 ; is a walk in the digraph ff of length at most k frorn u to v rvith cr(Il| = g-'h. This immediately implies the following result on the diarneter of the lift tcf.[]):

Lemma I Let a be a voltage assignment on a digraph ll in a group l. Then diant(ff) ! k if ancl onlv if for eaclt ordered pair of vertices u,t, of H Qtossibl.v u = v) ancl for each g e I there exists a valk of length < k front u lo t, whose net voltage is g.

For any verlex ,/ e /1 and auy non-negative integcr / let a[a;/] denote the set of all distinct voltages on closed walks in // of length / emanating from u. We norv have an obvious corollary of Leurma l:

Lemma 2 Let a be a voltage assignntent on a digraph II in a groupf . If the diameter of the lift I{u is equol to k, then for each vertex u e H,

\[\sum_{t=0}^{k} |\alpha[u;t]| \ge |\Gamma|\]

Proof. According to Letntna I (the case , = 1,), if diant(If) = k then for eacha e I/(ID and for each g e f there exists a closed u'alk at r of length < t u'hose net r,oltage is equal to g. In other u'ords, the union of all scts cr[rr;/], 0 < t < k, is equal to f; this proves our incqualitl'. a

4 Results

Recall that for d 2 3 and k > 2, by a (rlfr)-digraph l,e runderstand any diregular digraph of degree r/, diameter k and order I,Iat - l. Whcn referring to c.ycles of the rcpeat autolnorphisrn r \\'e nlean the cycles in the cycle decomposition of r, l'rittcn as a penllutation of Iz(G).

Thcorcm I Let G be a (3.k)4igroph,k> 3, and let r be lhe repeot autontorphism of G. Then oll cycles of r have equal length, snraller than 3nlog3kl(k + | - log3k).

Proof. Let I be tlte c1'clic subgroup of --1ul(G) gcncratcd by r. By Thcorcrn 3 of [6], f acts semi-regularly on I(G); let the size of each orbit of f on Z(G) be equal to nr. Consider the quoticnt digraph H = Glf and let I'(11) = q; clearly n = lIt(G)l = mq. In order to prove our thcorem it is sufficient to show that q > (ft + I log3k)/(3.log3/r).

Accorcling to Proposition l, thcre exists a voltage assignrnent cr on the quotient digraph /-/ in the (cyclic) group f such that the lift lf is isornorphic to the orrginal digraph G. Although u'e have no infornration about the stnlcture of the quotient digraph ff (except that it has g verlices, each of degree three), u,e ncvcrlheless may establish an uppcr bound on the nurnbcr of distinct volta!,es on its closed u,alks as follorvs.

Let x;, I 3 i <3q be the collection of all arcs of /1 and let c((xi) = ai e I be the corresponding voltages. Fix a vcrtex r/ e V(m and eslinrate the nurnber of elernents in thc set cr[r;l] for a fixed t < k. Let II/ be a closcd u'alk in l/ of length /, emanating frorn (and termiuating at) rr. Assume that thc u'alk lraverses 7; tirnes the arc x;, ltere

\[\sum_{i=1}^{3q} j_i = t\]. The net voltage of W is then \(\alpha(W) = \sum_{i=1}^{3q} j_i a\)

Frorn this rve irnmediately see that the nurnbcr of voltages appcaring in the set ct[u;t] is ncver grcater than the number of ordercd 3q-tLrplcs (it,...jt) of nonncgalive intcgers $'hose surn is equal to /. The nunrbcr of such ordercd dccornpositions is u'ell knoun to be equal to \(\binom{t+3q-1}{3q-1}\). For the number of possible

voltages on all closed walks at u of length \(\leq k\) we therefore obtain:

\[\sum_{t=0}^{k} |\alpha[u;t]| \le \sum_{t=0}^{k} {t+3q-1 \choose 3q-1} = {k+3q \choose 3q}\] (1)

Since \(diam(H^{\alpha}) = k\), by Lemma 2 and the inequality (1) we have \(|\Gamma| \le \binom{k+3q}{3q}\). Recalling that the lift \(H^{\alpha}\) is isomorphic to our (3,k)-digraph G with \(n = 3(3^k - 1)/2\) vertices and that \(|\Gamma| = m = n/q\), we obtain

\[\frac{3(3k-1)}{2q} \le \binom{k+3q}{3q} \tag{2}\]

In order to eliminate q, we observe that \(l \binom{k+l}{l} < k^{l+1}\)

for each \(k \ge 3\) and \(l \ge 1\). (Indeed, this is trivially true for l = 1,2, and an easy induction works for \(l \ge 2\).) Combining this inequality with (2) we finally obtain

\[3^{k+1} \le 2q \binom{k+3q}{3q} + 3 \le 3q \binom{k+3q}{3q} < k^{3q+1},\] and hence \(q > (k + 1 - \log_3 k)/(3\log_3 k)\). The proof is complete.

We have the following obvious corollary announced earlier.

Corollary 1 Let G be a (3,k)-digraph, \(k \ge 2\), and let r be the repeat automorphism of G. Then r cannot consist of a single cycle.

Proof. If \(k \ge 3\), the result follows directly from Theorem 1 because q > 1. For k = 2 it is sufficient to observe that the inequality (2) is not valid for q = 1.

The last result can be extended slightly by reformulating it in terms of Cayley digraphs. Let \(\Gamma\) be a (finite) group and let X be a generating set for \(\Gamma\). The Cayley digraph \(C(\Gamma,X)\) has vertex set \(\Gamma\), and for any ordered pair of vertices \(g,h \in \Gamma\) there is an arc emanating from g and terminating at h whenever gx = h for some \(x \in X\). We observe that \(C(\Gamma,X)\) is a vertex-transitive digraph of degree |X|; the group \(\Gamma\) acts regularly on the vertex set of the Cayley digraph by left translations.

Corollary 2 Let G be a (3,k)-digraph, \(k \ge 2\). Then G cannot be a Cayley digraph of an Abelian group.

Proof. Assume that a (3,k)-digraph G is isomorphic to a Cayley digraph \(C(\Gamma, X)\) where \(\Gamma\) is an Abelian group. Since \(\Gamma\) acts regularly on V(G), the quotient digraph \(G/\Gamma\)

consists of precisely one vertex incident to three loops. Examining the proof of Theorem 1 one quickly sees that it is valid for all Abelian (not only cyclic) groups. The Corollary follows.

Acknowledgement

This research was done while the first and the third authors were visiting the Department of Computer Science and Software Engineering of the University of Newcastle NSW Australia in June 1997, supported by P4M grant and ARC grant.