On the complete digraphs which are simply disconnected

Publicacions Ma emá iques, Vol 35 (1991), 517-525 . ON THE COMPLETE DIGRAPHS WHICH ARE SIMPLY DISCONNECTED Abs ac DAVIDE C . DEMARIA AND ,I . CARLOS S . KHHL Homo opic me hods a e employed o he cha ac e iza ion o he comple e dig aphs which a e he composi ion o non- i ial highly egula ou na- men s . 1 . In oduc ion I is known ha one can also cons uc a homo opy heo y o ca ego ies o spaces ha ing a s uc u e weake han a opology . Fo example, one can ake he ca ego y o p espaces o Cech closu e spaces . To e e y dig aph D one can associa e, in a na u al way, wo ini e p espaces P(D) and P* (D) ; and ice e sa, o e e y ini e p espace one can associa e wo dig aphs G and G*, dually o ien ed . Hence one can ela e he ca ego y o he dig aphs wi h ha o he ini e p espaces . The e o e a homo opy heo y can be de ined o dig aphs, by se ing he egula homo opy g oup Q ,(D) o D o be he homo opy g oup 7  ,(P(D)) o he associa ed p espace (see [6]) . In [3] Bu zio and Dema ia p o ed ha he g oups Q,(D) a e isomo phic o he classical homo opy g oups 7  ,(IKDI), whe e jKD1 is he polyhed on o a sui able simplicial compeex KD associa ed wi h he dig aph D . Then in [5] hey ob ained, as an applica ion o he egula homo opy o dig aphs, a s uc u al cha ac e iza ion o ou namen s T, called simply disconnec ed ou - namen s, whose undamen al g oup QI(T) is non i ial . In [4], hey ha e ob ained ano he cha ac e iza ion o he simply disconnec ed ou namen s by using coned 3-cycles . In his pape we ex end hose esul s o he case o dig aphs D which a e comple e, and we ge analogous esul s i QI(D) ~¿ 0 . Fi s o all, we mus gene alize he concep o simple quo ien o e e y ype o dig aph and we p o e he ollowing heo em : Theo em 4 .4 . E e y (non- i ial) dig aph has a unique simple quo ien . In his way we ob ain he ollowing heo ems : 518  D .C . DEMARIA, J .C .S . KIIHL Theo em 5 .3 . A comple e dig aph D is simply disconnec ed i and only i i s simple quo ien is a highly egula ou namen . Theo em 5 .10 . A comple e dig aph D n is simply disconnec ed i and only (a) he e exis s in D n a non coned 3-cycle ; (b) e e y symme ic pai and e e y 3-cycle in D n a e sh inkable in D n . 2 . Some De ini ions and No a ions De ini ion 2 .1 . Le V be a ini e non-emp y se and E a se o o de ed pai s (u, ) E V x V, such ha u =,A . We call he pai D = (V, E) a di ec ed g aph o dig aph . The elemen s o V a e he e ices o D, he ca dinali y o V he o de o D, and he elemen s o E he a es o D . Mo eo e , we w i e u -> ins ead o (u, ), and we call u a p edecesso o and a successo o u . Rema k 1 . Gi en wo dis inc e ices u and , we ha e a p io i ou possibili ies, and ou ypes o a e : (1) he e is no o ien ed a e be ween u and - we deno e by uI he null a e ; (2) he e is he o ien ed a e (u, ), bu no he a e ( , u) - we deno e he simple a e by u -> ; (3) he e is he o ien ed a e ( , u), bu no he a e (u, ) - we deno e he simple a e by u - ; (4) he e a e bo h o ien ed a es (u, ) and ( , u) - we deno e he double a e by u <--> . (A double a e is also called a symme ic pai .) De ini ion 2 .2 . A dig aph is called o ien ed i , be ween wo dis inc e ices, he e is a mos one o de ed a e - ha is, he possible a es a e ei he simple a es o null a es . A dig aph is called a non-o ien ed g aph i , be ween wo dis inc e ices, he e is ei he a double a e o a null a e . A dig aph is called comple e i , be ween wo dis inc e ices, he e is a leas one o de ed a e ; he possible a es in his case a e ei he simple o double a es . De ini ion 2 .3 . A dig aph T is a ou namen i , be ween e e y pai o dis inc e ices, he e is one and only one a e . A ou namen T is called hamil onian i i con ains a spanning cycle - ha is, a cycle passing h ough all he e ices o T . De ini ion 2 .4 . Le D = (V, E) and D' = (V', E') be dig aphs . A unc ion : V -> V' is a homomo phism be ween D and D' i , o e e y u, E V u -> implies ei he (u) -> ( ) o (u) = ( ) . Rema k 2 . We can conside wo kinds o duali ies o a gi en dig aph D : (a) he i s one is he dually o ien ed dig aph D, which is ob ained by changing he o ien a ion o he a es ; in his case, bo h dig aphs a e o he same ype . (b) he second kind is he dig aph D, which is ob ained by main aining he simple a es and by changing he null a es in o double a es, and ice- e sa . In ON COMPLETE DIGRAPHS  519 his case, o ien ed dig aphs become comple e dig aphs, and ice- e sa . On he o he hand, ou namen s and non-o ien ed g aphs do no change . I is known ha , gi en a ou namen T, we can associa e an algeb aic s uc- u e o T in a na u al way . In ac we ha e (see [ 7 1) : P oposi ion 2 .5 . A ou namen T becomes a commu a i e g oupoid A(T) i we de ine he ollowing bina y ope a ion * : Rema k 3 . Simila ly we can associa e wi h T he dual commu a i e g oup- oid A' (T ), by de ining : u, i u-> o u= ; o allu, ET,u* = *u=~ ,  i -> u . u, i -->uo u= ; o allu, ETu * = * u={ ,  i u --~ . Rema k 4 . E e y homomo phism be ween wo ou namen s T and T' is also an algeb aic homomo phism be ween he commu a i e g oupoids A (T) and A(T') (o A'(T) and A'(T')), and ice- e sa . The same de ini ions can be applied o he case o a dig aph D o any ype, and hen we ha e he associa ed g oupoids A(D) and A'(D), which a e dual . In his case, we se o A(D) : on he o he hand om uI we ge : Rema k 5 . In gene al he wo g oupoids a e no commu a i e . In he i s case, om u <--> we ge u * =uand * u= ; u* =uand *u=u . Rema k 6 . Whe eas he homomo phisms be ween wo ou namen s coin- cide wi h he algeb aic homomo phisms be ween he associa ed g oupoids, his is no ue in he gene al case, o he e a e homomo phisms be ween dig aphs which a e no algeb aic homomo phisms be ween he associa ed g oupoids . u, i u-~ o u= ; o all u, ED, u * , i 74 u ; and o A'(D) : u, i u 4 o u= ; o all u, E D, u * , i u --> . 52 0  D .C . DEMARIA, J .C .S . KIIHL Fo example, gi en he 3-cycle C : u , -> w - ; u and he symme ic pai D : x <--> y, i we de ine : C --+ D by (u) = x, ( ) = (w) = y, hen in A(C) and A(D)we ha e Rema k 7 . We can s ill associa e o he wo g oupoids l(D) and h(D) o he dig aph D, in he ollowing way : and u * w= w,  (u) * (w) = x * y = x and (w) = y . o allu, ED,u* u, i u= o u- ; ,  i u y L . o allu, cD, u* ={ u, i u= o ug¿- ; ,  i u <--V . We obse e ha , i we change he o ien a ion o he a cs, hen A(D) becomes A(D) and A'(D) becomes Á'(D) ; in changing he double a cs in o null a cs and he null a cs in o double a cs, A(D) becomes h(D), and A'(D) becomes A(D) . 3 . Quo ien Dig aphs We say ha a subse X o e ices o a dig aph D is a se o equi alen e ices i o any e ex u in D - X he o ien ed a cs om u o any e ex in X a e all o he same ype . O cou se he ype o o ien ed a c can change i we a y he e ex u in D - X . I p : A(D) -+ A(Q) is a su jec i e algeb aic homomo phism be ween he g oupoids which a e associa ed o he wo dig aphs D  and Q,  ,,, o o de n and m, espec i ely, hen we see ha he g oupoid A(Q) is isomo phic o he quo ien g oupoid A(D)/p . Fo , i we conside he m p e-images o he e ices ,, . . . ,  ,, in Q  ,,, and we se S(i) = p- ' ( i), i = 1, . . . , m, hen we can subdi ide he n e ices o D in m disjoin subdig aphs S( I ), . . . , S(-) o equi alen e ices, because he ype o a c which joins he e ex i o j is o he same ype as he a cs which join e e y e ex in S(i) o e e y e ex in SO) . I he abo e condi ions hold, hen we w i e D,, = Q,(S('), . . . , S(m)), and we say ha he dig aph D,, is he composi ion o he m dig aphs S(I), . . . , S(-) . The subdig aphs S ( ' ) ,.. . , S(n) a e called he componen e o he dig aph D, and Q  , is he quo ien o he dig aph D, n . We say ha a dig aph is simple i he composi ion D,, = Q,,,(S~ I) ,. . . , S(m)) implies ha m = 1 o m = n - ha is, i he quo ien Q  ,, o he componen e S( 2 ) coincide wi h he i ial dig aph o o de 1 . ON COMPLETE DIGRAPHS  52 1 4 . P ope ies o he Quo ien Dig aphs P oposi ion 4 .1 . Le D be a dig aph, Q be one o he quo ien dig aphs o D, and S be one o he componen s o D wi h espec o Q ; hen S is a se o equi alen e ices . Con e sely, i X is a se o equi alen e ices, hen X is a componen o D . P oo .. The i s s a emen is ob ious . Fo he second, we conside he pa - i ion o D in he subse X and he singula subse s o D - X P oposi ion 4 .2 . Le X and Y be wo se s o equi alen e ices o a dig aph D . I X l Y =,A 0 and X U Y =~ D, hen X U Y is a se o equi alen e ices . P oo .. Le u be a e ex in X n Y and le be a e ex in D - (X U Y) ; o each e ex w in X U Y, he o ien ed a c be ween and w is o he same ype as he o ien ed a c be ween and u P oposi ion 4 .3 . Le D be a dig aph and Q one o i s quo ien dig aphs ; hen Q is isomo phic o a subdig aph E o D . P oo . . In ac we can cons uc E by choosing one e ex in each componen s o D Theo em 4 .4 . E e y non- i ial dig aph has a unique simple quo ien . P oo .. We a gue by con adic ion .  Le P =  [S(1), . . . , S( h )] and Q  = [T('), . . . ,T( k )] be wo di e en pa i ions o he dig aph D in o componen s o equi alen e ices, such ha he quo ien dig aphs Ph and Qk a e non- i ial and simple . Then we ha e : D= Ph(S(1), . . . , S (h) ) = Qk(T (1) ,... ,T ( k )) . Suppose ha h > 2 . Since he wo pa i ions a e dis inc , he e mus exis wo dis inc componen s S and T wi h non emp y in e sec ion . I S is no con ained in T and he o he componen s T ha e non-emp y in e sec ion wi h S, hen a leas oneo hem canno be con ained in S, o o he wise we can eplace hese pa icula componen s T in he pa i ion Q by he unique componen S ; his con adic s he simplici y o Qk . The e o e he e exis a componen S and a componen T such ha S n T ,4 0, S ~ - T and T 9~- S, and we choose hem o be S(1) and T( 1 ) . We nownumbe he componen s S in such a way ha S( 1 ), S( 2 ), . . . , S( , ) in e sec T (1) , while he es S(T+1), S(T+2) . . .  S(h) do no in e sec T( 1 ) . We dis inguish wo cases : 522  D .C . DEMARIA, J .C .S . KIIHL (a) 1< <h . Since he componen s S( 1 ), S(2), . . . , S( ) in e sec T (1) , hei union U = S(1) U . . . U S( ) is a subse o equi alen e ices . Hence, o he pa i ion pl = [U, S( +1), S( +2) ... S(h)] we can associa e a new composi ion o D, which will induce a composi ion o Ph . Bu his con adic s he simplici y o Ph . (b) = h . The o ien ed a es be ween a e ex u in S(1) - T(1) and any e ex in he union U= S( 2 ) U S( 3 ) U . . . U S( h ) a e all o he same ype, because e e y componen S('), i = 2, 3, . . . , h in e sec s he componen T( 1 ) . On he o he hand, Since u is a e ex in S( 1 ), he o ien ed a es be ween any e ex in S(1) and any e ex in U a e o he same ype . This means ha he pa i ion [S( 1 ), U] is a composi ion o D, which is a con adic ion, o we ha e supposed ha he quo ien Ph is simple o o de h > 2 . Finally, i h = 2, hen k mus be also equal o 2, o o he wise i would be su icien o in e change he wo composi ions and epea he p e ious a gu- men . On he o he hand, he dig aphs P2 and Q2 mus be isomo phic, o i P2 is he null a e, hen he dig aph D is disconnec ed, i P2 is he simple a e, hen he dig aph D is weakly (bu no s ongly) connec ed ; and i P2 is he double a e, hen he dig aph D is s ongly connec ed Rema k 1 . I ollows om he p oo ha , o h > 2, we ha e no only a unique simple quo ien , bu also a unique pa i ion in o componen s . On he o he hand, o h = 2, hen we may ha e mo e pa i ions . Fo example, i D = [u, , w ; u H , u H w, H w] we ha e he ollowing pa i ions P = [[u, ], w],  Q= [u, w], ] and R = [[ , w], u] . Rema k 2 . We ecall ha a dig aph is hamil onian i heie is a cycle passing h ough all he e ices . We shall conside a symme ic pai as a hamil onian cycle . P oposi ion 4 .5 . A comple e dig aph is hamil onian i and only i each o i s (non- i ial) quo ien s is hamil onian . P oo . F om esul s due o Rado (1943), Rey (1958) and Camion (1959), we know ha a comple e dig aph D is hamil onian i and only i he ou namen T 2 ( he simple o ien ed a e) is no he simple ou namen ela ed o D . We now obse e ha ei he he ini ial dig aph o any o i s quo ien dig aphs ha e he same simple quo ien . The asse ion ollows ON COMPLETE DIGRAPHS  52 3 5 . Comple e Dig aphs which a e Simply Disconnec ed De ini ion 5 .1 . A ou namen T is egula i , o each e ex E T, he numbe s o p edecesso s and successo s o a e he same (and hence he o de o T is odd) . A ou namen T2 .+1 is highly egula i he e exis s a cyclical o de ing i, . . . , 2n,,+1, Vi on he e ices o T2  ,, + 1 such ha i -~ j i and only i j is one o he i s m successo s o i in he cyclical o de ing o T2 .+1 . De ini ion 5 .2 . A dig aph D is simply connec ed i i s i s homo opy g oup Q 1 (D) is i ial . A dig aph D is simply disconnec ed i Q 1 (D) is non- i ial . We ha e he ollowing heo em : Theo em 5 .3 . A comple e dig aph D is simply disconnec ed i and only i i s simple quo ien is a highly egula ou namen . This heo em is a gene aliza ion o he analogous heo em o ou namen s (see Theo em 3 .9, o [5]) . Fo he p oo , we need he ollowing lemmas . Lemma 5 .4 . A comple e dig aph D is simply connec ed i and only i each o i s non- i ial quo ien dig aphs D* is simply connec ed . P oo . . This is analogous o he p oo o P oposi ion 2 .1 in [5] o ou na- men s Lemma 5 .5 . Fo e e y comple e dig aph D n o o de n, he e exis s a leas one ou namen o o de n which is a subdig aph o D n . P oo .. I is su icien o elimina e one o ien ed a c om each symme ic pai Lemma 5 .6 . Le D  , and F n be wo gi en comple e dig aphs, each o o de n, such ha Fn, is a subdig aph o D n . Then i F n is simply connec ed, so is D, . P oo .. Each edge-loop in he polyhed on associa ed o he dig aph D n is null-homo opic, since i is null-homo opic in he sub-polyhed on associa ed o he dig aph F n We now p o e Theo em 5 .3 : (a) I he simple quo ien o a comple e dig aph D is a highly egula ou - namen , hen D is simply disconnec ed . This ollows di ec 1y om Lemma 5 .4 and he ac ha a highly egula ou namen is simply disconnec ed . (b) Le D n be a comple e dig aph which is simply disconnec ed ; hen D n , has a highly egula ou namen as a simple quo ien . 52 4  D .C . DEMARIA, J .C .S . KIIHL A ou namen T  , which is a subdig aph o D  , is aleo simply disconnec ed, and he e o e is he composi ion o a highly egula ou namen , by he analo- gous heo em o ou namen s . I is now su icien o p e e ha he simple a es which ough o be eplaced by double a es in o de o pase om he ou namen T  o he ini ial comple e dig aph D,,, all belong o sub ou namen s which a e componen e o T, z . FYom Lemma 5 .4, we see ha he eplacemen o simple a es by double a es in he componen s o T  ,, do no change he i s homo opy g oup o he dig aphs which a e ob ained one by one . On he o he hand, i we assume he e exis s a double a e wi h e ices u and , which belongs o wo di e en componen s o T  ,, hen : 1) i we cons uc a 3-cycle C in T  , using he e ices u and , hen he edge-loop de e mined by C is no null-homo opic in he polyhed on associa ed o T  ,, as i is a gene a o o QI(T~,) (see [5, P oposi ion 3 .6]) ; 2) en he o he hand, i we eplace he simple a e be ween u and by a double a e, hen he same loop becomes null-homo opic in he polyhed on associa ed wi h he comple e dig aph ob ained in such a manne om T,, . The e o e he i s homo opy g oup o such a dig aph is i ial, and hence by Lemma 5 .6 he g oup Ql(D~) is aleo i ial . Hence he esul ollows Co olla y 5 .7 . A simply disconnec ed comple e dig aph is hamil onian . P oo . This ollows easily om P oposi ion 4 .5 Be o e we ob ain a second cha ac e iza ion o he simply disconnec ed com- ple e dig aphs, we need o in oduce some u he de ini ions . De ini ion 5 .8 . A subdig aph F o a dig aph D is coned i he e is a leas one e ex u in D - F, such ha u is ei he a p edecesso o a successo o he e ices in F ; o he wise, he subdig aph E is non-coned . De ini ion 5 .9 . A subdig aph F o a dig aph D is sh inkable i he e exis s a p ope subse o D consis ing o equi alen e ices, and con aining F . Theo em 5 .10 . A comple e dig aph D . is simply disconnec ed i and only i (a) he e exis s in D n , a non-coned 3-cycle ; (b) e e y symme ic pai and e e y coned 3-cycle in D  , a e sh inkable in D n , . P oo .. By Theo em 5 .3, i is su icien o show ha a comple e dig aph whose simply quo ien is a highly egula ou namen , is cha ac e ized by he condi ions (a) and (b) . 1) The p oo ha condi ions (a) and (b) a e necessa y is analogous o ha gi en o ou namen s in [4, Th . 7] . ON COMPLETE DIGRAPHS  52 5 2) I we suppose ha condi ions (a) and (b) hold o he comple e dig aph D, hen by (b) he simple quo ien dig aph Q o D  , is a ou namen , such ha each o i s 3-cycle is non-coned . Hence by he analogous heo em o ou namen s which was men ioned abo e and by he simplici y o Q, we see ha he ou namen Q is highly egula . The esul is p o ed Aknowledgemen s . This wo k was pe o med unde he auspices o he Consiglio Nazionale delle Rice che (CNR, GNSAGA) and o FAPESP (P oc . NQ 89/2042-1) . Re e ences 1 . BEINEKE, L . W . AND REID, K . B ., Tou namen s, in "Selec ed Topics in G aph Theo y," Edi ed by L . W . Beineke and R . J . Wilson, Academic P ess, New Yo k, 1978 . 2 .  BURZIO, M . AND DEMARIA, D . C ., Duali y heo em o egula homo- opy o ini e di ec ed g aphs, Rend . Ci c . Ma . Pale mo (2), 31 (1982), 371-400 . 3 .  BURZIO, M . AND DEMARIA, D . C ., Homo opy o polyhed a and egula homo opy o ini e di ec ed g aphs, A i II° Con . Topologia, Suppl . Rend . Ci c . Ma . Pale m o (2), 12 (1986), 189-204 . 4 .  BURZIO, M . AND DEMARIA, D . C ., Cha ac e iza ion o ou namen s by coned 3-cycles, Ac a Uni . Ca ol . Ma h . Phys . 2 8 (1987), 25-30 . 5 .  BURZIO, M . AND DEMARIA, D . C ., On simply disconnec ed ou namen s, P oc . Ca ania ConE, A s Combina o ia 24 A (1988), 149-161 . 6 .  DEMARIA D . C . AND GARBACCIO BOGIN R ., Homo opy and homology in p e opological spaces, P oc . 11 h Win e School, Suppl . Rend . Ci c . Ma . Pale m o (2), 3 (1984), 119-126 . 7 .  MÜLLER, V ., NESETRIL J . AND PELANT J ., Ei he ou namen s o alge- b as?, Disc e e Ma h . 11 (1975), 37-66 . Da ide C . Dema ia : Dipa imen o di Ma emá ica Uni e si á di To ino ia P incipe Amedeo 8 10123 To ino ITALIA J . Ca los S . Kiihl : Depa amen o de Ma emá ica IMECC-UNICAMP Caixa Pos al 6065 13081 - Campinas, SP BRASIL Rebu el 28 de Gene de 1991