Open Journal of Discrete Mathematics, 2011, 1, 103107 doi:10.4236/ojdm.2011.13013 Published Online October 2011 (http://www.SciRP.org/journal/ojdm) Copyright © 2011 SciRes. OJDM Symmetric Digraphs from Powers Modulo n Guixin Deng1*, Pingzhi Yuan2 1School of Mathematics, Guang xi Teachers Educati o n U ni versity, Nanning, China 2School of Mathematics, South China Normal University, Guangzhou, China Email: *oldlao@163.com, mcsypz@mail.sysu.edu.cn Received June 21, 2011; revised July 25, 2011; accepted August 5, 2011 Abstract For each pair of positive integers n and k, let G(n,k) denote the digraph whose set of vertices i s H = {0,1,2,···, n – 1} and there is a directed edge from a H to b H if ak b(mod n). The digraph G(n,k) is symmetric if its connected components can be partitioned into isomorphic pairs. In this paper we obtain all symmetric G (n,k). Keywords: Congruence, Digraph, Component, Height, Cycle 1. Introduction In [12], L. Szalay showed that is symmetric if or . In [1], the authors proved that if p is a Fermat prime, then is not symmetric when or , but it is symmet ric when . And the following theorem is part of Theorem 5.1 in [13]. ,2Gn 8 5r 2mod4n k 4modn 3r 2,2 r Gp 4 Theorem 1.1 ([13] Theorem 5.1) Let 12 nnn , where 12 and . Suppose that 1, where . Then is symmetric if one of the following conditions holds: 1, 1nn mm12 gcd ()1nn ,Gnk 2n1 i) and 2, 2,mk 1 2; mk ii) and 3, 2,mk 2 2; mk iii) and 4m2k In this paper we prove that if is symmetric, where and ,Gnk 2km 2n, then or m, k satisfy one of the conditions of the above theorem. 5,m4k The outline of this paper is as follows. In Section 3 we obtain all symmetric by direct computation. In Section 4 we prove some properties about digraph products which will be useful in the proof of our main theorem. In Section 5 we state and prove the main theo rem of the present paper. 2, m Gk 2. The Carmichael LambdaFunction Before proceeding further, we need to review some pro perties of the Carmichael lambdafunction . n Definition 2.1 Let n be a positive integer. Then the Carmichaellambdafunction n is defined as follows: 12 2 1 12 1 11, 21, 42, 22 if 3, 1 if is odd prime, lcm ,,, ir kk kk reee e ir i k ppp pan ppp p where pi are distinc primes. The following theorem generalizes the wellknown Euler’s theorem which says that if and only if 1mod n an gcd ,1an . Theorem 2.1 (Camichael). Let Then ,.ana n 1mod n ord g if and only if . Moreover, there exists an integer g such that where denotes the multiplicative order of g modulo n. 1an n ordg gcd , ,n n For the proof see [5 , p. 21] 3. The Case n = 2m Let G be a digraph and a be a vertex in G. The indegree of a, denoted by ind(a) is the number of directed edges coming to a, and the outdegree of a is the number of edges leaving a. Particularly, let denote the indegree of a vertex a contained in indk na ,Gnk. There are two particular subdigraphs of ,Gnk. Let 1,Gnk be the induced subdigraph of on the set of vertices which are coprime to n and ,Gnk 2,Gnk be the induced subdigraph of on the set of vertices which are not coprime with n. We observe that ,Gnk k 1 Gn,
G. X. DENG ET AL. 104 and are disjoint and that 2,Gnk ,Gnk 2 , that is, no edges goes between and. 1 ,k G ,k 1,Gnk k Gn nk Gn 2,Gn ,Gn . A , 2 It is clear that each component of contains a unique cycle, since the component has only a finite number of vertices and each vertex has outdegree 1. The following lemma tells us that every component contained in is determined by its cycle length. k nd ,Gnk 1t ,Gnk Lemma 3.1 ([13] Corollary 6.4) Let be a fixed integer. Then any two components in con taining tcycle are isomorphic. 1 Definition 3.1 We define a height function on the ver tices and components of . Let c be a vertex of , we define hcto be the minimal nonnegative integer i such that i k c iongruent modulo n to a cycle vertex in ,Gnk if C is a component of ,Gnk c s ,Gnk, e suhC we de in ind fin 1,Gnk d 2 i .hc p ei i kk n p cC The indegree and the height function play an impor tant role in the structure of . We need the fol lowing results concerning the indegrees and heights. ,Gnk p i Lemma 3.2 ([14]) Let be the prime 1i r i e i n factorization of n. Let a be a vertex of positive indegree in . Then 11 gcd rr ii , , i e i apak where if 2k and 8i e i p, and 1 i , ek other wise. Lemma 3.3 ([11] Theorem 3.2) Let p be a prime. Let a be a vertex of positive indegree in , and assume that 2 Gp l p ind e p 2 k and . Then for some positive integer t and 0alkt l k 1gcd , kt ke ap p where if 2,2pk and and 3,el 1 otherwise. Lemma 3.4 ([13] Lemma 3.2) Let p be a prime and e, k be two positive integers. Then ind 0. e e e kk pp Lemma 3.5 Let p be a prime and be two positive integers. Let h be the positive integer such 2,e2k that . Then 1 ke hh k 2, e hhGpk , e pGpk . Proof. It is clear that and 2 hp And ,. e p k 2 hG 0mod k pp ie v if and only if This proves the Lemma.□ .e i k Lemma 3.6 Let p be a prime and be two positive integers. Let ,ek2 e pu where u is the maxi mal divisor of relatively prime to k. If G is the component of containing 1, then e p , e Gp k min :i hC ivk Proof. Let min :. i hivk Then there exists a di visor d of v such that d is not a divisor of 1h k . By Theorem 2.1 there exists a vertex , e Gpk such that . e p ord guv Let mod uv e d ag p . Then e p ord a d and 1h k a is not congruent modulo to 1, but e p od1m k a he p. We have by the definition of height functio n. hC hh a Conversely if ,aC then there exists such that 1j , ke 1mod jap then . e p orda k Bu t , e p orda uv hence . e p orda v And 1mod . h k ae p That is .hhC Lemma 3.6 is proved.□ Now we can prove our first result. Theorem 3.1 Let be two positive inte gers. Then 2, 1km 2, m Gkis symmetric if and only if one of the following conditions holds. i) 1;m ii) 2,2 ;mk iii) 4, 2;mk iv) 5, 4;mk v) 2m 3, 2,.mkkm Proof. The case 3m follows directly by simple computations, so we may assume that , thus 3m 2 22 m . We first suppose that is sym metric. Let 0 and 1 be the components of 2, mkG C C 2, m Gk containing the vertex 0 and 1, respectively. Then it is easy to see that 0 is just 2. Since the cycle lengths of 0 and 1 C are 1, by the assump tions and Lemma 3.1 we must have, thus C 2, m Gk 0 CC 1 C 01 hChhC 1h. If , then k and m gcd 1nd 2,ki2m 02d1m in , where 1 if k is odd, and 2 if 2k. We must have 2 2mk . If 2k , then 1 is a cycle, however is not a cycle. Hence we may assume that C0 C 2,kr1 r and 2h. We have 2 2m 1min:i hhCi k by Lemma 3.6. It implies that 12rhm rh. (3.1) Since 0 hhC, by Lemma 3.5 we have 1. h kmk h (3.2) Combining (3.1) and (3.2), we obtain 11 21 rh h kmrh1, so 3h and 2r . By an easy computation, we have 56,4,2,2 , 5,2,3,1,, ,mkhr ,4,2,2 , or 4,2,2,1 . 16,2G By computations we know that both and 32,4G are symmetric. For and 32,2G ,464G, Copyright © 2011 SciRes. OJDM
105 G. X. DENG ET AL. by Lemmas 3.2 and 3.3, we have , and for any vertex a in 1 which has positive indegree, . Similarly , 2 32 ind 48 16 C 2 32 ind 4a4 64 ind 16 a 8 4 64 ind . Thus neither of them are symmetric. Finally, from Theorem 1.1 it is clear that if m, k satisfy one of i)  v), then is symmetric. Theorem 3.1 is proved.□ 2, m kG G 4. Properties of Digraphs Product Given two digraphs 1 and 2 G. Let 12 G be the digraph whose vertices are the ordered pairs G 12 ,,aa where i and there is a directed edge from i aG 12 ,aa b 12 1,nn to if there is a directed edge from i to i for In [13] L. Somer and M. Krizek proved the following fact: Let where 12 ,bb 1,2.ia gcd , 12 nnn then 12 And the canonical isomorphism is given by where Gnk ,,nk Gnk ,. 12 ,aaa Ga In general we have mod , ii an Gnk r i i n 12 gcd ,nn 1,2. ,,k i ,r ee r k Gp nnn ,k 12 12 e Gp, p Gp if 1 is the prime factorization of n. We need this fact and the following lemma. i e Lemma 4.1 ([4] Lemma 3.1) Let 12 where . Let i C be a component of 1 , i Gnk 12 . And the cycle length of i C is i. Then tCC is a subdigraph of Gn consisting of com ponents, each having cycles of length . ,k 12 gcd ,tt 12 lcm ,tt 12 gcd ,nn 1Lemma 4.2 Let 12 where nnn . If is symmetric, then is symmetric. 1,Gnk Gn Gn 12 k Gn ,k (,) k Proof. It follows immediately from Lemma 4.1 and the fact .□ ,,k k Gn ,GnLemma 4.3 If is symmetric, then ,r Gnk is also symmetric for any . 1r ,Gnk Proof. Assume that has 2m components, say, 12 2 and for each there exists an isomorphism ,,,m CC C,1, 2,,im i of digraphs: :. mii i CC d If two vertices x, y are in the same component of , then there exists a vertex z and positive inte gers u, v and ,r Gnk mo u k zn, which implies that x, y are in the same component of mod v k yz n ,Gnk . It follows that if D is a component of , then there exists a such that ,r Gnk 2,j 2m1, , DC. Let 1 1 s 1 i and where CD2 1 s mj iE 1 C D, 1 and , are components of . If 1, 2,,js ,r Gnk l E 1 2 s1, 2,,l , yC and mod , r k yn 1mod k then there exist such that 12 ,,yy, r yy , yn and 1mo d k ii . y n So 1 k 1 mod yn and k i y 1 11 mo i d , n we get 11 r k mo d yn and 1 still preserves arrows e consider 1 C and 1m C if w as subdigraphf s o ,r k 12 Gn It fo s llows that and 1 is still an isomor phism if we consid1 C as subdigraphs of er 1 C and m ,r Gnk . Hence Gn is asymmetric. Lemma ved.□ Let G be adigra ,r kls h. Let o 4.3 is proG d genote the number of vertices in G, and let ax . cG m Gindc Lemma 4.4 Let G dand Ho digraphs, an be tw ,aG .Hb Then ind ,indind,abab HMG , GMH and GHGH . Proof of th ve . It follows imhmediately from te definitions.□ The following lemma is the key lemma for the prf oo he digraph whose set of e main result of this paper. Lemma 4.5 Let m O denote t rtices is 011 , , m aaa and there is a directed edge from ,a i a to a if ph and on o ly if 0j aaa. Let G and H be twdigras such that all vertices and H have outdegree 1. Then mm OGOH if and only if GH. in G :mm OGOH et Proof. Assume that is an iso morphism of digraphs. L 0ind 0GxG x , 1ind 0GxG x, 00HxHindx , 10HxHindx . and If 1 G ind ,ind0,axaind x th en d 0. Lin ,ax et ' ,,, j axa x then we have '1 H and . j aa Np 11 1 :GHow we define a ma by ', 1 x1. G Obviously, 1 is inj If ective. '1, H ethe exists a vex ,ay of pn therrteosi tive iin m OG ndegree such that '.ay Hence ,,ay ' 1yy and 1 is also surjecti Now that 1 ve. we assume, yG, and there is a directed edge from x to y. Let '' ,, 11 xyy by defini tion we have x ax ' , and ,a ,ay ' ,.ay We know that there is a directed edge from ,ax to ,,ay then there is also a directed edge from to ' ,ax ' ,ay since preserves arrows. So there a dd edge from ' is also irecte and ' . We showed that 1 preserves arrows. For any 1 yG , let 10 is a directed edge from to , there is a directed ed ge from to , xGx y xGx y y d the above union is a disjoin union since each 00 thereEy Ey then An ve 1 00 yG GE t rtex has outdegree 1. If ' 1yy , by Lemma 4.4 we have 01 '' 01 ' , ind, aym EyEy aym EyEy indeg Copyright © 2011 SciRes. OJDM
G. X. DENG ET AL. 106 and ' 11 Ey Ey maps 1 Ey since 1 into . Then we also have ' 1 Ey '. 00 Ey Nowe ne a map Ey w can defi0 from to 0 0 G such that for any 0 x E, 0. 0 1 Ey Fily we can define :GH nal ii aaaG fo if , r 0,1.i It is easy to show that is bijective. Now we prove that preserve arrows. Suppose , yG needand therdge from x to y. We e is a directed e onlyto treat the case when 0 G and y1 G . Le ' t 1 yyy . By the construction of 0 we ' 00 , see that xEy so there is also a arrow from to . It is easy to show that the number of direcis equal to the number of dicted edges of te d edges of G H. Thus re is anorphism. Lemma 4.5 is proved.□ 5. The Main Theorem o begi n wi isom Tth, we pr o ve the fol l owing lemma. component ofLemma 5.1 Let E be the 64 ,4Gq be another phic to F. lid. containing the vertex 0 where q is odd and F is where pr component of 64 ,4Gq. Then E is not isomor An d the similar result for 32,2Gq is also va Proof. We only prove the case for 64 ,4Gq, the proof for 32Gsimilar and we omit the details. Assume that 1i re i i qp each i p is an odd ,2q ime, and 2 i e if ,is 1 i e if . ir ve Let 0 or C and i C the components of 64,4G and containing the rtex 1, and let i e i Gp ,4 , and 1, 2,,ir n 10 . r ECC C of F > 1, then F is not isomorhic to hat the cycle length o respectively. The 00 If the cycle length p E. Suppose tf F is 1, by L emma 4.1 12 , r CFF F where Fi is a component of cycle length 1 contained in ,4 i e i Gp . By Lemma 3.1 we can write 01 1, r r CC C wher 0 or 1. By computations we know that e By Lemma .3 there exists i 16, such 01 8.MC MC 1 i uthat 0 i 3 i u i Cp or if 2, i u i p or 4i u i p1 ,is 01 i if . MC ir And by Lemma 3.2 1,4 2 or 4. for any 1i gcd 11i e ii MCpp i hus 6 , s i i MC .r T 00 11 16 1 r i i ME MC 1 () i ri i MF MCMC . Now if (), EMF 0 we have and if 12 0 s , 0 then all i0, .EF If 01, then 1 r and 2gcd 1, r pk. But in th case is 0 1 0 1 32 . i ii ri i C p FC C 1rr1 0 11 11 ,  i e i r EC C Therefore we have EMF or EF, E is not isomorphic to Fed. Theorem 5.1 (Main Theorem) Let and n . Lemma 5.1 is prov□ 2k 2, mq where and q is odd1m . Then k is ,Gn symmetric if and only if 2, m Gk is symmetric. ove thProof. By Lemma 4.2 we only need to pre ne cessity. The case 1m is trivial, so we may ass 2m. Lbe the component of ume that et 0 C containing the vertex 0,be the compon2, m Gk ent of and 1 C 2, mk containing the vertex 1. Let G 00 hhC and 11 hhC. We cthat laim 2k and 01 .hh Other wise ume firstly that k is odd or 01 .hh In cases we have we ass both 01 22 2,,m h m GkO and if 0 2,h m Gk 0,x and then 01 2 ind2. h m km x By Lemma 4.3 0 ,h Gnk is alsoetric and symm , m 0 , h Gnk G Let H 0 2, h k Gqk s 0 . h where each 0 ,, hii i Gqk m 1 i is a connect cent such that ompon ij H if any ifd onl ,ij and ij HMH for .ij We choossuch cane an l that l m is odd and 2 m if ,jlince 0 ,h Gqk is not symmetric. s Then 01 2, l h m i k m is als ii HG o symmetric. Let 0 ,, h ml EkH by Lemma 4.1 E connected en 22G pon t is a com of 0 2,h mi since 1 l i i mGk H 0 22,h m Gk is a co1. Let F be another comm nent of ponent of cycle length po 1. ii imH Suppose that by Lemma 4.1 again F is a component of , i 0 2,h ml ,EF Gk H where K i 0 ,h mk and 1il s a component of. 2G But we have 1 2 1 2 ml m l i EMO H MH KMH MF Copyright © 2011 SciRes. OJDM
G. X. DENG ET AL. Copyright © 2011 SciRes. OJDM 107 where the equality holds if and only if 1 2m MK [2] G. Chartrand and L. Lesnid Edition),” Chapman Hall, London, 1996 k, “Graphs and Digraphs (3rd . dulo a Prime,” and , il HMH which implies 0 22, . h m KG k But now we have 0 22,h mi Gk OHOH H a . nd [3] WunSeng Chou and Igor E. Shparlinski, “On the Cycle Structure of Repeated Exponentiation Mo 11 22 mm li Hence li H by Lemma 4.5We show that there , il. are exactly ml components contained in 0 2,h m Gk lmH 1ii i It is contrary to th 0 h which are isomorphic to E. e fact that is symmetric. have Journal of Number Theory, Vol.107, No. 2, 2004, pp. 345356. doi:10.1016/j.jnt.2004.04.005 [4] Joe KramerMiller, “Structural Properties of Power Di graphs Mudulo n,” Manuscript. lmH [5] M. Krizek, F. Lucas and L. Somer, “17 Lectures on the Femat Numbers, from Number 1 2, mii i Gk Theory to Geometry,” Quart, Vol. 34, 1996, pp. the Theory of Numbers,” 5th Edition, 148, No. 123, Springer, New York, 2001. [6] C. Lucheta, E. Miller and C. Reiter, “Digraphs from Pow ers Modulo p,” Fibonacci Now we2,k if 01 ,hhnsider co Wd Using the same arguments we can show that 226239. [7] I. Niven, H. S. Zuckerman and H. L. Montgomery, “An Introduction to 111 12 2, 2,2, hhh mmm GkGkGk. e have 11 12 2, m h m GkO an M John Wiley & Sons, New York, 1991. [8] T. D. Rogers, “The Graph of the Square Mapping on the Prime Fields,” Discrete Mathematics, Vol. 11 2,2,. hh mm GkMGk 21 1996, pp. 317324. doi:10.1016/0012365X(94)00250M [9] L. Somer and M. Krizek, “On a Connection of Number Theory with Graph Theory,” Czechoslovak Mathematic 1 ,h Gnk , we have is not symmetric. Hence then for any v m if a is eve lies that is 01.hhh ert If 1,hex a 0m k an and , o d. It im et 2, m G k 1moda 1 2 2 . m GkO d2 is odp symm ric in this case. 2 km 2, m Gk Journal, Vol. 54, No. 2, 2004, pp. 465485. doi:10.1023/B:CMAJ.0000042385.93571.58 [10] L. Somer and M. Krizek, “Structure of Dig ated with Quadratic Congruences with if a 2, mrphs Associ Composite If 1,h then 3.m Assume that 2rk have (3.1) and (3.2), by orem ha , then we the proof of The 3.1 (4, 2). Then is comd by rem 3.1. k be two positive integers is symmetric if and only if rem No. 1, 2 Moduli,” Discrete Mathematics, Vol. 306, No. 18, 2006, pp. 21742185. doi:10.1016/j.disc.2005.12.026 [11] L. Somer and M. Krizek, “On Semiregular Digraphs of the Congruence xk y(mod n),” Commentation we ve (= (5, 4), (6, 4), (5, 2) or the proof Lemma 5.1 and Theo Corollary 5.1 Let n,and 2,1 mnm. Then G k = 1 m, k) plete □ es Mathe ud. KÄozl, Vol. 8, 1992, pp. 7191. ematics, Vol. maticae Universitatis Carolinae, Vol. 48, No. 1, 2007, pp. 4158. [12] L. Szalay, “A Discrete Iteration in Number Theory,” BDTF T ,nk one oor k, m satisfyf (i)  (v) in Theo 3.1. 6. References [1] [13] L. Somer and M. Krizek, “On Symmetric Digrphs of the Congruence xk y (mod n),” Discrete Math 309, No. 8, 2009, pp. 19992009. doi:10.1016/j.disc.2008.04.009 [14] B. Wilson, “Power Digraphs M Quart, Vol. 36, 1998, pp. 229239. W. Carlip and M. Mincheva, “Symmetry of Iteration Digraphs,” Czechoslovak Mathematic Journal, Vol. 58, 008, pp. 131145. doi:10.1007/s1058700800098 odulo n,” Fibonacci
