The n-th Root of a Digraph Dennis Paul Gellerl Logic of Computers Group The University of Michigan Abstract For any digraph D and any n>2, necessary and sufficient conditions are given for there to be a digraph E such that En=D. The absolute n-th power is defined, and a characterization of digraphs which can be expressed as the absolute n-th power of another digraph is also given. 1Research supported by National Institutesof Health (GM-12236) and the National Science Foundation (GJ-519).

I A —4 < - W Z- --

Graphs and digraphs having at least one square root have been characterized in [1] and [2]. In this note we extend the results of those papers and, for any n a 2, given necessary and sufficient conditions for a digraph to have an n-th root. Let D = (V,X) be a digraph. We represent the adjacency relation on D by rD; thus rD(u) = {vluveD} and rDl(u) = {vlvueD}. The n-th power Dn of D is a digraph with V(Dn) = V(D) and uveDn if and only if there is a walk of length at most n from u to v in D. Let S1,S2,...,S2n_1 be sets, not necessarily disjoint, subject to the constraints that Sn / P and if Snj = b(S n+j=) then for all k > j Sn-k = O(Sn+k=). Let K = Kn(Sl,...,2n-1) be the digraph with 2n-1 n-l 2n-2 V(K) US and X(K = [SX(SnU...USn+j)]U[ J Sjx(S j+... ) j1 jl n' j=n Theorem 1: Let D be a digraph and let n 2 2. There exists a digraph E such that En=D if and only if there is a collection of subdigraphs Ki = Kn(Si lb.'*Si,2n-l) of D associated with the points u; of D such that (1) Si,n = {ui } (2) X(D) = UX(Ki) (3) uiS jn-. if and only if ujS in+l (4) for any O<r<n-l and s=r+l: uk Si,n-s if and only if there is a ujcSin-r such that UksSjn-l; UkcSin+s if and only if there is a u cSin+r such that ukSj n+l' Proof: Let E be a digraph. For each uieE define Sij to be rnE (ui); in particular Sin = {u.}. In En, for each l<jsn-l, each point of S.,n i.1 -,

is adjacent to each point of i,n' S in+l't, in+J' each point of Sij is adjacent to each point of Si,j+l,..,*Si, 2nl.1 Each arc uiuj of En is determined by a path u iUk...uj of length r<n, so that UiESk,n-1 and u jSkn+r, and hence u jujKk. Conditions (3) and (4) follow from the properties of rE~ Conversely, let D have such a collection. Define a digraph E by setting V(E) = V(D) and u ujcE just when uiESjn We show that En=D by demonstrating that, for each u. and each l<k<2n-, Sik = rk-n(ui). It will then follow that uju jEn if and only if uiujeD. For, if u ujED, u uj is in some Kk; thus for some r and s, uieSk,r and ujcESk,S, where r<n<s and ssr+n. Then there is a n( u) such that uStl' so that uiut EE, and ut eSk,r+l1 We then find t2 such that ut ut 2E and 1 1 tl12 ut ESk r+2; we continue until we find tb such that ut ut b and 2' UbE a utb Sk,nl, so that utbukCE. Similarly we find a sequence tdtd -l...,tb+2, where d = s-r-l, such that uk ut 2Utdb+2Utb+2'' td j are all arcs of D. This defines a walk of length s-rsn between ui and uj in E; thus U U EEn. If u u cEn then ui and uj are joined by a walk uut t.. ut u k 1k of length at most n. Now, uijerE(ut ) = and uitr (u) = St 1 t1,n-1 t tl 1 Since k<n, n+k<n+(n-l); thus u ujcD. k-n (u If k = n-l then We proceed to show that Si,k = rE If k = n-l then rkn (ui) = rEl( ui): {ujluluicE} = {ujlu jSin l}:= Sk. If k = n+l, rk-n (u) = rE(u) = {uj juijUE} = {ujluiSj,n-l}. But uiSjn just when ujES i,n+l; thus rE(ui) = Sin+l~ Suppose the result holds for n-r<k<n+r, and let s=r+l. Then r n-s)-n(ui = - (u i) = r ( E = (i,n-r1 = U {rEl(uj)lujESi,nr}. For any uj,rE (uj) = Sjn Thus if (,j) and uj. Snr then up=Snr-l =S n- On the other hand,

if upcSinr_1 then there is a uj such that upCSj and u CS p i,n-1 j i,n-r$ so that up rE (u)cE S n-r = rEl (rEr(ui)) = rsE(ui). Similarly, we can show that Si,n+s. = rS(ui) establishing the theorem. The theorems in [1] and [2] follow as corollaries for the case n=2. The absolute n-th power D<n> of D has V(D<n>) = V(D), and uvcD<n> if there is a walk of length exactly n joining u and v in D. Let 2n-1 H = Hn(S1l..S,2n-1) be the digraph with V(H) = U S. and n- j= X(H) = jlLj x Sj+n]. The proof of the next theorem is virtually identical to that of Theorem 1. Theorem 2: Let D be a digraph and n~2. There is a digraph E such that En = D if and only if there is a collection H. = Hn(Sl,...,S2n_1) associated with the points ui of D which satisfies conditions (1) - (4) of Theorem 1. Corolla': A digraph D has an absolute square root if and only if there are sets Si and Ti associated with the points ui of D such that (1) each point of Si is adjacent to each point of Ti; (2) for each arc x of D there is some u. for which x joins Si and Ti; and (3) ujESj if and only if uj Ti. Corollary: A graph G has an absolute square root if and only if there is a collection of complete subgraphs Ki associated with the points ui of G such that G = UJKi and ujiKj if and only if ujeKi. References 1. Geller, D., "The Square Root of a Digraph," J. Combinatorial Theory, 5, (1968), 320-321. 2. Mukhopadhyay, A., "The Square Root of a Graph," 3. Combinatorial Theory, 2, (1967), 290-295. --

cO (0 01 c - z 00 00 Mo