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