UNIVERSIDAD NACIONAL AUTÓNOMA
DE MÉXICO
FACULTAD DE CIENCIAS
CONDICIONES SUFICIENTES PARA LA EXISTENCIA
DE NÚCLEOS POR TRAYECTORIAS DIRIGIDAS
MONOCROMÁTICAS.
T E S I S
QUE PARA OBTENER EL TÍTULO DE:
MATEMÁTICA
PRESENTA:
ALEJANDRA SILVA RAMÍREZ
DIRECTORA DE TESIS:
DRA. MUCUY-KAK DEL CARMEN GUEVARA AGUIRRE
2017
CIUDAD UNIVERSITARIA, CDMX.
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
  
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
  
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
  
 
Tabla de Contenidos
1. Introducción 1
2. Nociones básicas 3
3. Resultados preliminares 8
3.1. Digráficas Cuasitransitivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2. Núcleos en Digráficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4. Resultados 15
5. Conclusiones 32
6. Bibliografía 33
1
Índice de figuras
2.1. Cuasitransitividad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Estos ciclos C6 son cuasitransitivos en el borde ya que tienen las flechas [v0, v2],
[v1, v3], [v2, v4], [v3, v5], [v4, v0]. . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3. Torneos de orden 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4. Ejemplo de D y su C (D) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1. [x1, x3] ∈ F(D). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2. [x5, x1] ∈ F(D). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3. D[P] es semicompleta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4. Las trayectorias del Corolario 3.1. . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1. El ciclo Ck presentado en el lema. . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2. [ui, vs] ∈ F(D). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3. El ciclo C claramente es policromático. . . . . . . . . . . . . . . . . . . . . . 20
4.4. [ui, v1] ∈ F(D). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.5. [ui, v2] ∈ F(D). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.6. C∗ es de longitud 4 y no es cuasimonocromático . . . . . . . . . . . . . . . . . 22
4.7. La longitud de C1 es t + 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.8. Aqui se pueden ver los casos de la observación 3. . . . . . . . . . . . . . . . . 23
4.9. Representacion del ciclo C′. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.10. Representación del ciclo C′′ . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.11. Aqui se puede observar que pasa con α∗ ≥ q − 2. . . . . . . . . . . . . . . . . 25
4.12. Para β∗ = t − q + 3 tenemos este ciclo. . . . . . . . . . . . . . . . . . . . . . . 25
4.13. Representacion del ciclo C′′′ para β∗ < t − q + 3. . . . . . . . . . . . . . . . . 26
4.14. Representación del ciclo propuesto en el inciso a. . . . . . . . . . . . . . . . . 26
4.15. Representacion del ciclo que se da en el inciso b. . . . . . . . . . . . . . . . . 27
4.16. Si β∗ > α∗ + 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.17. Si β∗ = α∗ + 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.18. Para β∗ = α∗ + 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.19. Si β∗ < α∗. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.20. El ciclo Ck del teorema 4.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2
Capítulo 1
Introducción
El concepto de núcleo en digráficas es introduccido en 1944 por J. von Neumann y O. Mor-
genstern [6]. Un núcleo de una digráfica es un conjunto de vértices absorbente e independiente.
Debido a que existen digráficas sin núcleo se buscan condiciones necesarias o suficientes
para la existencia de núcleos. Algunas condiciones suficientes para que una digráfica tenga nú-
cleo son que D sea simétrica, que D no contenga ciclos impares, que D sea acíclica y que D sea
transitiva.
Además se ha ido extendiendo este concepto de diversas maneras generando así los cua-
sinúcleos, seminúcleos y a los (k, l)-núcleos; y para familias particulares, como los torneos y
digráficas cuasitransitivas entre otras.
También se ha estudiado la existencia de núcleos por trayectorias dirigidas monocromáticas,
el cual es el tema central del presente trabajo.
En 1982, B. Sands, N. Sauer y R. Woodrow [7] probaron que las digráficas 2-coloreadas
tienen núcleo por trayectoria dirigidas monocromáticas, en particular esto se cumple para los
torneos 2-coloreados.
Por lo que de manera natural surgió el siguiente problema: ¿Todo torneo m- coloreado tiene
núcleo por trayectorias dirigidas monocromáticas?, y la respuesta es no, ya que si al torneo C3
lo coloreamos exactamente con tres colores podemos observar fácilmente que este no contiene
núcleo.
De tal manera que el problema se modificó al siguiente: ¿Si T es un torneo m-coloreado sin
triángulos dirigidos policromáticos entonces T tiene núcleo por trayectorias dirigidas monocromáticas?.
En 1988 Shen Miggang probó que si T es un torneo m-coloreado sin triángulos(ni dirigidos,
ni transitivos) policromáticos entonces T tiene núcleo por trayectorias dirigidas monocromá-
1
ticas resolviendo de manera parcial el problema planteado por Sands, Sauer y Wodrow [7].
Además Shen Minggag mostró que la condición de no tener C3 y TT3 no puede ser mejorada
ya que dio ejemplos de torneos que tienen C3 y no TT3 y viceversa que no tienen núcleo en [8].
Posteriormente H.Galeana-Sánchez y R.Rojas Monroy [5] mostraron la existencia de tor-
neos 4-coloreados sin triángulos dirigidos C3 y sin torneos transitivos TT3 policromáticos que
no tienen núcleo. Actualmente para m = 3 es un problema abierto.
En este trabajo se estudian los resultados de H. Galeana-Sánchez, Bernado Llano y Juan
José Montellano-Ballesteros plasmados en el artículo: Núcleos por trayectorias dirigidas mo-
nocromáticas en digáficas m-coloreadas con clases cromáticas cuasitransitivas [3], donde se
preguntan por la existencia de núcleos por trayectorias dirigidas monocromáticas en digráficas
sin triángulos dirigidos policromáticos, donde sus clases cromáticas son cuasitransitivas y sus
ciclos son cuasitransitivos en el borde. Particularmente se observan condiciones para que los
torneos pertenecientes a esta familia de digráficas m-coloreadas tengan núcleo por trayectorias
dirigidas monocromáticas. De tal manera que se responde parcialmente a la pregunta para los
torneos 3-coloreados.
2
Capítulo 2
Nociones básicas
En este capítulo daremos un breve repaso a las definiciones básicas de digráficas y de algu-
nos resultados que utilizaremos en el presente trabajo.
Una gráfica dirigida o digráfica D, es un par ordenado de conjuntos (V(D), F(D)) tal que
F(D) ⊂ V(D) × V(D), donde D(V) es el conjunto de vértices, no vacío, y F(D) es un conjunto
de pares ordenados de elementos distintos de V(D) llamados flechas. En este trabajo V(D) es
finito y llamaremos a D una digráfica finita.
Se denotará [u, v] ∈ F(D) cuando (u, v) ∈ F(D) ó (v, u) ∈ F(D). Y [u, v] < F(D), en caso
de que (u, v) < F(D) y (v, u) < F(D). Esta notación nos ayudará a asegurar la existencia de la
flecha entre u y v sin indicarnos la dirección.
La flecha (u, v) en D será simétrica si (v, u) ∈ F(D); y asimétrica cuando (v, u) < F(D).
La digráfica H es una subdigráfica de la digráfica D si: V(H) ⊆ V(D) y F(H) ⊆ F(D).
Una subdigráfica generadora H cumple que V(H) = V(D). H es una subdigráfica indu-
cida si cumple que V(H) ⊆ V(D) y tiene al conjunto de flechas dado por F(D) ⊂ V(H)xV(H).
Para S ⊆ V(D) y A ⊆ F(D) se denotará como D[S ] a la subdigráfica inducida por el con-
junto de vértices y D[A] a la subdigráfica inducida por el conjunto de flechas A.
Una digráfica D es simétrica (respectivamente asimétrica) si cada flecha en ella es simé-
trica (respectivamente asimétrica).
La parte asimétrica (respectivamente simétrica) de D, Asim(D) (respectivamente Sim(D)),
es la subdigráfica generadora de D con el conjunto de flechas asimétricas (respectivamente si-
métricas) que pertenecen a D.
3
Una trayectoria dirigida P = (u = x0, . . . , xk = v), es una sucesión de vértices distintos tal
que (xi, xi+1) ∈ F(D) para 0 ≤ i < k. P es una (u, v)-trayectoria dirigida donde u es el vértice
inicial y v el terminal.
La longitud de una trayectoria dirigida P, denotada por ℓ(P), se define como el número
de flechas contenidas en la trayectoria. Por ejemplo, si P es una trayectoria dirigida tal que
P = (x0, . . . , xk), entonces ℓ(P) = k.
Un ciclo dirigido,C = (xo, . . . , xk, x0) es una sucesión de vértices distintos tales que cum-
plen (xi, xi+1) ∈ F(D) con i ∈ {1, . . . , k} modulo k + 1. Notación: Cl representa un ciclo de
longitud l.
Una digráfica D es cuasitransitiva, si para {u, v,w} ⊂ V(D) tal que {(u, v), (v,w)} ⊂ F(D) se
tiene que [u,w] ∈ F(D) (véase Figura 2.1).
Figura 2.1: Cuasitransitividad.
Sea C = (x1, . . . , xk, x1) un ciclo en D, con k ≥ 2, C es cuasitransitivo en el borde si cum-
ple que para cada i ∈ {1, 2, . . . , k} existe [xi, xi+2] ∈ F(D) (véase Figura 2.2).
4
Figura 2.2: Estos ciclos C6 son cuasitransitivos en el borde ya que tienen las flechas [v0, v2],
[v1, v3], [v2, v4], [v3, v5], [v4, v0].
Una digráfica es semicompleta, si entre todo par de vértices u y v, existe al menos una
flecha en D.
Un torneo T es una digráfica semicompleta con una sola orientación en cada una de sus
flechas. Los únicos torneos de orden 3 son el C3 y el TT3 a los cuales llamaremos triángulos
(véase Figura 2.3).
Figura 2.3: Torneos de orden 3
Sean S ⊆ V(D). S es un conjunto independiente si para todo par de vértices u, v en S , se
tiene que [v, u] < F(D).
Sea K ⊂ V(D), definimos a K como núcleo de D si cumple:
1. K es un conjunto independiente, y
2. para cada u ∈ V(D) \ K existe una flecha (u, v) para algún v ∈ K.
5
Llamaremos a D núcleo perfecta (denotada por N.P.) si cada subdigráfica inducida de D
tiene núcleo, y núcleo imperfecta critica (denotada por N.I.C.) si D no tiene núcleo pero todas
las subdigráficas inducidas propias sí.
Una digráfica es m-coloreada si sus flechas estan coloreadas con exactamente m colores.
Una digráfica H es llamada cuasimonocromática si tiene solo una flecha de color distinto,
H es policromática si sus flechas tienen al menos 3 colores y monocromática si estan colo-
readas con un solo color. Se denotara a las trayectorias dirigidas monocromáticas como t.d.m.
Al conjunto F de flechas del mismo color en D lo llamaremos una clase cromática. Si la
subdigráfica inducida por F es cuasitransitiva, diremos que F es una clase monocromática
cuasitransitiva.
Sea S ⊆ V(D), S es un conjunto independiente por trayectorias dirigidas monocró-
maticas, si cumple que para todo par de vértices u, v ∈ V(S ), no existen (u, v)-trayectoria y
(v, u)-trayectoria dirigidas monocromáticas.
Sea S ⊆ V(D), S es conjunto absorbente por trayectorias dirigidas monocromáticas, si
para cada u ∈ V(D) \ S existe v ∈ S tal que hay una (u, v)-trayectoria dirigida monocromática
en D.
Sean D una digráfica m-coloreada y K ⊆ V(D), K es llamado núcleo por trayectorias
dirigidas monocromáticas si:
1. K es independiente por t.d.m. y
2. K es absorbente por t.d.m.
La cerradura de una digráfica D m-coloreda, denotada por C (D) (véase Figura 2.4), es la
digráfica que cumple:
1. V(C (D)) = V(D)
2. F(C (D)) = F(D) ∪ {(u, v) de color i si existe una (u, v) − trayectoria de color i}.
6
Figura 2.4: Ejemplo de D y su C (D)
La exvecindad de un vértice v se define como N+(v) = {w ∈ V(D) \ v | (v.w) ∈ F(D)}
La invecindad de un vértice v se define como N−(v) = {w ∈ V(D) \ v | (w, v) ∈ F(D)}
7
Capítulo 3
Resultados preliminares
3.1. Digráficas Cuasitransitivas
Empezaremos demostrando algunas propiedades de las digráficas cuasitransitivas que serán
herramientas para saber como se dan las adaycencias entre vértices.
La siguiente proposición nos será de gran utilidad para justificar la existencia de flechas
entre vértices y además nos indicara la dirección que tienen.
Proposición 3.1. Sean D una digráfica cuasitransitiva y P = (x1, x2, . . . , xk) una trayectoria
dirigida de longitud mínima. Si k , 4 tenemos que D[V(P)] es una digráfica semicompleta y
(x j, xi) ∈ F(D) para cada j > i + 1, 1 < i, j < k. Mientras que para k = 4, la flecha (x4, x1)
puede no estar en D.
Demostración 3.1. Para k , 4, procedamos por inducción sobre k.
Si k = 1 y k = 2 la proposición se cumple por vacuidad. Ahora para k = 3 se tiene que
P = (x1, x2, x3). Por ser D cuasintrasitiva y P de longitud mínima tenemos que (x3, x1) ∈ F(D).
Si k = 5, P = (x1, x2, x3, x4, x5). Por ser D cuasitransitiva [x1, x3] ∈ F(D), si (x1, x3) ∈ F(D),
entonces P no sería de longitud mínima, por lo tanto (x3, x1) ∈ F(D), (véase Figura 3.1). Análo-
gamente se demuestra que {(x4, x2), (x5, x3)} ⊆ F(D). Ya que tenemos la trayectoria (x5, x3, x1)
y como D es cuasitransitiva [x5, x1] ∈ F(D). Pero si (x1, x5) ∈ F(D), se contradice la longitud
mínima de P, (véase Figura 3.4). De manera similar por la trayectoria (x5, x1, x2) se tiene que
(x5, x2) ∈ F(D) y por (x4, x5, x1) tenemos que (x4, x1) ∈ F(D). Con este conjunto de flechas la
subdigráfica inducida por los vértices de P es una digráfica semicompleta y (x j, xi) ∈ F(D) con
j > i + 1.(véase Figura 3.3)
8
Figura 3.1: [x1, x3] ∈ F(D).
Figura 3.2: [x5, x1] ∈ F(D).
Figura 3.3: D[P] es semicompleta.
Supondremos ahora que para toda P = (x1, . . . , xn) de longitud mínima con 5 < n < k, se
cumple que D[V(P)] es semicompleta y (x j, xi) ∈ F(D), con j > i + 1 y 1 < i < n − 1.
Sea P′ = (x1, . . . , xk) de longitud mínima. Por demostrar que D[V(P′)] es semicompleta y
(x j, xi) ∈ F(D), con j > i + 1, 1 < i, j < k.
Tomemos a P∗ = (x1, x2, . . . , xk−1) que es una (x1, xk−1)-trayectoria de longitud mínima. Por
hipótesis de inducción D[V(P∗)] es semicompleta y (x j, xi) ∈ F(D) para i ∈ {1, 2, 3, . . . , k − 2}
con j > i+1. Ya que (xk−2, xk−1), (xk−1, xk) ∈ F(D), por ser D cuasitransitiva [xk−2, xk] ∈ F(D). Si
(xk−2, xk) ∈ F(D) se tendría la (x1, xk) trayectoria de longitud menor, así que (xk, xk−2) ∈ F(D).
Por hipótesis de inducción (xk−2, x j) ∈ F(D) para j ∈ {1, 2, 3, . . . , k − 4}. Y además tenemos
a (xk, xk−2) ∈ F(D). Como D es cuasintrasitiva [x j, xk] ∈ F(D) con j ∈ {1, 2, . . . , k − 4}. Si
9
(x j, xk) ∈ F(D) se podría construir una (x1, xk)-trayectoria de longitud menor, por lo tanto
(xk, x j) ∈ F(D).
Veamos que pasa con xk−3. Tenemos que las flechas (xk, xk−4) y (xk−4, xk−3) ∈ F(D), pero ya
que la trayectoria P′ es de longitud mínima (xk−3, xk) < F(D). Así que (xk, xk−3) ∈ F(D), De
manera similar se muestra que (xk, xk−i) ∈ F(D) para i ∈ {4, 5, . . . , k − 2}.
Así D[V(P′)] es semicompleta y (x j, xi) ∈ F(D) para toda j > i + 1.
Para el caso k = 4. Sea P = (x1, x2, x3, x4). Por ser D cuasitransitiva y P de longitud mínima
tenemos que (x3, x1) y (x4, x2) ∈ F(D). Si estuviera (x1, x4) ∈ F(D) la trayectoria no sería mí-
nima. Para asegurar la existencia de (x4, x1), deberían haber (x4, x1)-trayectorias de longitud
2, pero en D[V(P)] no las hay; sin embargo, no sabemos si en D existen. Es por eso que no es
posible asegurar la existencia de la flecha (x4, x1) ∈ F(D). 
Los siguientes dos corolarios mostrarán resultados particulares que nos serán de gran ayuda
para demostrar los teoremas posteriores en los que se busca que D tenga núcleo.
Corolario 3.1. Si D es una digráfica cuasitransitiva y existe una (x, y)-trayectoria dirigida, pe-
ro (x, y) < F(D), entonces (y, x) ∈ F(D) ó existen vértices u, v ∈ V(D)\{x, y} tales que (x, u, v, y)
y (y, u, v, x) son trayectorias dirigidas en D.
Figura 3.4: Las trayectorias del Corolario 3.1.
Demostración 3.2. Sea P una (x, y)-trayectoria de longitud mínima k.
Para k , 4 por la proposición 3.1 (y, x) ∈ F(D).
Si k = 4, tenemos a P = (x, u, v, y) y por la proposición 3.1 , se tiene que (v, x) y (y, u). Por
lo tanto tenemos las trayectorias (x, u, v, y) y (y, u, v, x) en D.
10
Corolario 3.2. Sea D una digráfica cuasitransitiva la cual tiene una (x, y)-trayectoria pero no
(y, x)-trayectoria, entonces (x, y) ∈ F(D).
Demostración 3.3. Sea P = (x1, x2, . . . , xk) una (x, y)-trayectoria y supongamos que no hay
una (y, x)-trayectoria en D.
Entonces k ∈ {1, 4} ya que de lo contrario, por la proposición 3.1, se tendría que existe una
(y, x)-trayectoria dirigida en D, pero eso es una contradicción a la hipótesis.
Si k = 4, entonces por el corolario 3.1 existe una (x, y)-trayectoria dirigida, por lo que
nuevamente tenemos una contradicción.
Por lo tanto k = 1, es decir, P = (x, y).
3.2. Núcleos en Digráficas
En esta sección se presentan dos teoremas de J. Bang-Jensen y P. Duchet [2] los cuales serán
nuestras herramientas para demostrar la existencia de núcleos en digráficas cuasitransitivas.
Sin embargo, primero veamos el siguiente resultado que nos facilitará la demostración de
uno de ellos.
Teorema 3.1. Toda digráfica D núcleo imperfecta crítica es fuertemente conexa.
Demostración 3.4. Procedamos por contradición. Sea D una digráfica núcleo imperfecta crí-
tica y supongamos que no es fuerte. Sea T una componente terminal y tomemos a S 1 el núcleo
de T.
Ya que D no posee núcleo el conjunto M = V(D) \ (N−(S 1) ∪ S 1) es no vacío. Ahora como
D es N.I.C. tenemos que D[M] tiene núcleo llamémoslo S 2. Observemos que S 1 ∪ S 2 es núcleo
de D.
Demostraremos que (S 1∪S 2) cumple las propiedades de núcleo. Sea {u, v} ⊆ (S 1∪S 2), note-
mos que [u, v] < F(D). Si {u, v} ⊆ S i con i ∈ {1, 2}, como S i es núcleo es claro que [u, v] < F(D).
Supongamos sin pérdida de generalidad que u ∈ S 1 y v ∈ S 2, sí (v, u) ∈ F(D), eso implica que
v ∈ N−(S 1), pero sabemos que v ∈ M, por lo tanto no hay tal flecha. Como S 1 es un conjunto
de vértices de una componente terminal y v ∈ S 1, tenemos que no hay flecha que vaya de u a v.
Por lo tanto [u, v] < F(D).
11
Nos falta ver que es un conjunto absorbente, sea w ∈ V(D) \ (S 1 ∪ S 2), de tal manera que
tenemos estas dos opciones; si s ∈ M \ S 2 en tal caso hay flecha entre w y S 2 por lo que es
absorbido y por otro lado si w ∈ N−(S 1) es claramente absorbido por S 1.
Por lo tanto támbien es un conjunto absorbente, quedando demostrado que S 1 ∪ S 2 es nú-
cleo de D.
De tal manera que llegamos a una contradicción por lo tanto D es fuertemente conexa. 
El siguiente Teorema nos da una caraterística específica en los ciclos para asegurar que D
contenga núcleo.
Teorema 3.2. Si cada ciclo dirigido de D tiene una flecha simétrica, entonces D es núcleo
perfecta.
Demostración 3.5. Sea D una digráfica tal que cada ciclo dirigido C tiene al menos una flecha
simétrica, es decir, D no contiene ciclos dirigidos asimétricos.
Supongamos que D no es núcleo perfecta, entonces existe una subdigráfica H inducida de
D que es núcleo imperfecta crítica (esto se puede hacer ya que D es finita).
Por lo tanto la H es fuertemente conexa por el teorema 3.1 , de tal manera que H contiene
un ciclo dirigido C∗ el cual es asmimétrico.
Pero C∗ también pertenece a D y es asimétrico; esto es una contradicción ya que todo ciclo
de D tiene una flecha simétrica, por lo tanto D es núcleo perfecta.
A continuación se presenta uno de los resultados más importantes tanto en núcleos como
en núcleos por trayectorias dirigidas monocroáticas dandonos una condición suficiente para en-
contrar ambos tipos de núcleos.
Teorema 3.3. Sea D una digráfica m-coloreada. D tiene núcleo por trayectorias dirigidas mo-
nocromáticas si y solo si C (D) tiene núcleo.
Demostración 3.6. Sea D una digráfica m-coloreada.
Sea N un núcleo por t.d.m. en D. Por demostrar que N es núcleo en C (D). Primero vea-
mos que N es un conjunto independiente en C (D). Sea {u, v} ⊆ V(N). Como N es núcleo por
t.d.m. en D, entonces no existen (u, v)-t.d.m. y (v, u)-t.d.m en D ya que N es independiente por
12
t.d.m. Por lo tanto, [u, v] < F(C (D)) por definición de cerradura. Nos falta ver que N es un
conjunto absorbente en C (D). Sea w ∈ V(C (D) \ N), como V(C (D)) = V(D) y N es núcleo
por t.d.m. de D, entonces existe una (w, v)-t.d.m en D para algúnv ∈ V(N), lo que implica que
(w, v) ∈ F(C (D)) por lo tanto N absorbe.
Así que N es un conjunto independiente y absorbente en C (D), entonces N es núcleo de
C (D).
Ahora sea N un núcleo en C (D). Por demostrar que N es núcleo por t.d.m. en D. Mostremos
que N es un conjunto independiente por t.d.m. en D. Sea {u, v} ⊆ V(N), como N es un conjunto
independiente en C (D) entonces no existe [u, v] ∈ F(C (D)). Ahora por definición de cerradura
tenemos que no hay (u, v)-t.d.m. y (v, u)-t.d.m. en D. Solo falta ver que N es un conjunto absor-
bente por t.d.m. en D. Sea w ∈ V(D) \ N y u ∈ V(N), ya que V(C (D)) = V(D) y N es núcleo
de D, existe (w, u) ∈ C (D) por lo tanto hay una (w, u)-t.d.m. Con lo que concluimos que N es
un conjunto independiente y absorbente por t.d.m. en D, entonces N es núcleo por t.d.m. en D. 
En la siguiente observación explicaremos como se utilizan los teoremas para encontrar nú-
cleo por trayectorias dirigidas monocromáticas, de tal manera que tengámosla muy presente.
Observación 1). Para probar que una digráfica tiene núcleo por trayectorias dirigidas mo-
nocromáticas, se demostrará que la cerradura tiene núcleo. De tal manera que se buscará que
todos los ciclos en C (D) contengan una flecha simétrica, es por eso que partiremos tomando
ciclos asimétricos en la C (D) y así llegar a una contradicción. He ahí la importancia de citar en
este trabajo los teoremas 3.2 y 3.3 fundamentales en la existencia de núcleos por trayectorias
dirigidas monocromáticas.
Con el siguiente lema dejamos claro el por qué trabajamos con ciclos en la C (D).
Lema 3.1. Sea D una digráfica m-coloreada tal que cada clase cromática es cuasitransitiva.
Si Ck es un ciclo en Asim(C (D)) entonces Ck es un ciclo en Asim(D).
Demostración 3.7. Sea Ck = (x1, x2, ....xk) ⊂ Asim(C (D)). Probemos que (xi, xi+1) ∈ Asim(D).
Como (xi, xi+1) ∈ Asim(C (D)), se tiene que (xi+1, xi) < (F(C (D)). Por lo que existe una
(xi, xi+1)-trayectoria monocromática en D, pero no hay una (xi+1, xi)-trayectoria monocromá-
tica en D. De tal manera que se cumple la hipótesi del corolario 3.2, entonces tenemos que
(xi, xi+1) ∈ F(D). Nos falta probar que (xi+1, xi) < F(D). Sí (xi+1, xi) ∈ F(D) tenemos una con-
tradicción ya que (xi, xi+1) ∈ Asim(C (D)). Por lo tanto (xi+1, xi) < F(D).
Con lo que queda demostrado que Ck es un ciclo en la parte asimétrica de D.
13
Observación 2). Si D es una digráfica m-coloreada y Ck un ciclo asimétrico en Asim(C (D)),
entonces existe un vértice en Ck tal que el ciclo cambia de color. Dado que Ck pertenece a
Asim(C (D)), entonces para cada {u, v} ⊆ (Ck) con (u, v) ∈ F(Ck) tenemos una (u.v)-trayectoria,
ahora si fuera todo el ciclo de un solo color podríamos construir una (v, u)-trayectoria mono-
cromática con lo cual tendríamos que la flecha (u, v) sería simétrica en la (C (D)), lo cual no es
posible porque Ck es asimétrico. Por lo tanto existe ui ∈ Ck donde hay un cambio de color.
14
Capítulo 4
Resultados
En este capítulo de la tesis presentaremos los resultados obtenidos por H. Galeana-Sánchez,
Bernado Llano y Juan José Montellano-Ballesteros [3], quienes trabajan con digráficas que tie-
nen como principales características el que poseen clases cromáticas cuasitransitivas y ciclos
cuasitransitivos en el borde, además de que estas no contienen triángulos dirigidos policromáti-
cos. Mientras que en el último teorema se le pedirá a la digráfica que sea asimétrica.
Iniciemos con el siguiente lema que nos será de gran utilidad.
Lema 4.1. Sea D una digráfica m-coloreada tal que :
a) cada ciclo es cuasitransitivo en el borde,
b) D no contiene triángulos policromáticos,
Supongamos que k > 3, Ck = (u0, u1, . . . , uk−1, u0) es un ciclo dirigido en Asim(C (D)) de
longitud mínima y para alguna i ∈ {0, 1, . . . , k}, ui es un vértice donde Ck cambia de color A a B.
Entonces:
1) (ui+1, ui−1) < F(D); (ui−1, ui+1) ∈ F(D) y
2) existe una (ui+1, ui−1)-trayectoria dirigida monocromática de color G, con G , {A, B} y
que no pasa por ui.
Demostración 4.1. Sea Ck = (u0, u1, . . . , uk−1, u0) un ciclo dirigido en Asim(C (D)) de longitud
mínima y ui un vértice donde Ck cambia de color A a B; es decir, (ui−1, ui) es de color A y
(ui, ui+1) de color B (véase Figura 4.1).
15
Figura 4.1: El ciclo Ck presentado en el lema.
Por hipotésis sabemos que todos los ciclos son cuasitransitivos en el borde y como tenemos
a {(ui−1, ui), (ui, ui+1)} ⊂ F(Ck) se tiene que [ui+1.ui−1] ∈ F(D).
Probemos que se cumple 1).
Supongamos por contradicción que (ui+1, ui−1) ∈ F(D). Si (ui+1, ui−1) es de color A, como
(ui−1, ui) es de color A, entonces se tendría la (ui+1, ui−1, ui)-t.d.m. de color A. Por lo tanto en
(ui+1, ui) ∈ F(C (D)), lo cual contradice que Ck está en Asim(C (D)),
Análogamente si (ui+1, ui−1) fuera de color B, se tendría que (ui, ui−1) ∈ F(C (D)) contradi-
ciendo que Ck es asimétrico en C (D). Entonces (ui+1, ui−1) tiene que ser de color distinto a A
y B. En este caso tendríamos un triángulo 3-coloreado, por lo que llegamos a una contradic-
ción ya que tenemos como hipótesis que D no contiene triángulos policromáticos. Por lo que
(ui+1, ui−1) < F(D) y como cada ciclo es cuasitransitivo en el borde se tiene (ui−1, ui+1) ∈ F(D).
Nos falta ver que ocurre 2).
Primero demostraremos que existe P = (ui+1, v1, v2, . . . , vt, ui−1) una (ui+1, ui−1)-t.d.m en D.
Supongamos que no existe tal trayectoria. Como (ui−1, ui+1) ∈ F(D), tenemos que (ui−1, ui+1) ∈
F(C (D)). Sí (ui−1, ui+1) ∈ Asim(C (D)), el ciclo C∗ = (u0,C, ui−1) ∪ (ui−1, ui+1) ∪ (ui+1,C, u0)
estariá en Asim(C (D)) y sería de longitud menor a Ck. Por lo tanto (ui−1, ui+1) < (Asim(C (D)),
es decir existe una (ui+1, ui−1)-t.d.m
16
Observemos que ui < V(P). De lo contrario si ui = u j tal que u j ∈ V(P), entonces tendría-
mos una (ui, ui−1)-t.d.m. lo cual implicaría que (ui, ui−1) ∈ F(C (D)), esto contradice la asimetría
de Ck.
Finalmente veamos de qué color es P. Supongamos que es de color A. Como tenemos la
flecha (ui−1, ui+1) de color A, entonces existe la (ui+1, ui)-t.d.m de color A. Por lo que (ui+1, ui)
pertenece a F(C (D)), pero (ui, ui+1) ∈ Asim(C (D)) lo que nos lleva a una contradicción. Análo-
gamente si la (ui+1, ui−1)-t.d.m fuera de color B. Por lo tanto la trayectoria P es de un color
distinto a A y B.
Así el lema se cumple.
Empezemos con los teoremas principales de este trabajo para reconocer a las digráficas que
poseen núcleo por trayectorias dirigidas monocromáticas.
Teorema 4.1. Sea D una digráfica m-coloreada tal que:
a) cada clase cromática es cuasitransitiva;
b) cada ciclo es cuasitransitivo en el borde, y
c) D no contiene triángulos policromáticos.
Entonces D tiene núcleo por trayectorias dirigidas monocromáticas.
Demostración 4.2. Tomando en cuenta el análisis en la observación 1 demostraremos que para
cada Ck ∈ C (D), Ck contiene una flecha simétrica.
Procedamos por contradicción:
Sea Ck = (u0, u1, ..., uk−1, u0) un ciclo asimétrico en la C (D) de longitud mínima, y tomemos
a ui ∈ V(Ck) el vértice donde Ck cambia de color A a B, es decir, (ui−1, ui) es de color A y
(ui.ui+1) de color B.
Por hipótesis cada ciclo es cuasitransitivo en el borde, entonces por el Lema 4.1 , tenemos
que (ui+1, ui−1) < F(D), pero (ui−1, ui+1) ∈ F(D) y existe una P = (ui+1, ui−1)-trayectoria mono-
cromática de color distinto a A y B, digamos G . Sabemos que (ui−1, ui+1) no es de color G, ya
que en caso contrario, la subdidigráfica generada por el conjunto {ui−1, ui, ui+1} nos formaría
un triángulo policromático en D, lo cual es una contradicción a la condición (c).
17
A la subdigráfica inducida por la clase cromática G, llamemosla H le aplicaremos el Co-
rolario 3.1; dado que G cumple ser cuasitransitiva y contiene una (ui+1, ui−1)-t.d.m y como
(ui−1, ui+1) < F(H); se tiene que existen vértices {vs, vl} ∈ V(H) \ {ui−1, ui+1} y con s , l tales que
(ui+1, vs, vl, ui−1) y (ui−1, vs, vl, ui+1) son trayectorias dirigidas en H.
Observemos que la subdigráfica generada por el conjunto {ui, ui+1, vs, ui} nos genera un
triángulo en D, el cual no puede ser policromático, así que la flecha [ui, vs] solo puede tener
color G ó B. Si [ui, vs] es de color G, tenemos una (ui, vs, vl, ui−1)-t.d.m o una (ui+1, vs, ui)-t.d.m
en C (D) ambas de color G, lo cual contradice que Ck es asimétrico en C (D) (véase Figura 4.2).
Figura 4.2: [ui, vs] ∈ F(D).
Por lo tanto [ui, vs] es de color B; con lo que obtenemos un triángulo policromático induci-
do por el conjunto {ui, vs, ui−1}, ya que (ui−1, ui) es de color A, (ui−1, vs) de color G y [ui, vs] es
de color B, lo cual no es posible.
Con lo que queda demostrado que todo Ck tiene una flecha simétrica lo que implica que
C (D) tiene núcleo. Por lo tanto D tiene núcleo por t.d.m.
El siguiente corolario se desprende de manera casi inmediata ya que los torneos son parte
de las digráficas cuasitransitivas.
Corolario 4.1. Sea T un torneo m-coloreado tal que:
a) cada clase cromática es cuasitransitiva; y
b) T no contiene triángulos policromáticos.
18
Entonces T tiene núcleo por trayectorias dirigidas monocromáticas.
Demostración 4.3. Sea T un torneo tal que cumple que cada clase cromática es cuasitransiti-
va y no contiene triángulos policrómaticos. Observemos que en T cada ciclo por sí mismo es
cuasitransitivo en el borde. Por lo tanto T cumple todas las hipotésis del teorema 4.1. Así T
tiene núcleo por t.d.m.
En el siguiente teorema se modificará la hipótesis c), que aparece en el Teorema 4.1 ya que
no solo se le pedirá que no contega triángulos policromáticos, si no que los ciclos dirigidos más
pequeños que q, para alguna q ∈ N, con q ≥ 4; no sean policromáticos y que los de longitud q
sean cuasimonocromáticos que son caracteriśticas muy específicas.
Teorema 4.2. Sea D una digráfica m-coloreada tal que:
a) cada clase cromática es cuasitransitiva,
b) cada ciclo es cuasitransitivo en el borde,
c) existe un número natural q ≥ 4, tal que cada Cq es cuasimonocromático y cada Cl, con
3 ≤ l ≤ q − 1 no es policromático.
Entonces D tiene núcleo por trayectorias dirigidas monocromáticas.
Demostración 4.4. Procederemos de manera similar que en el teorema anterior con base en la
observación 1. Sean Ck = (u0, u1, . . . , uk−1, u0) un ciclo dirigido asimétrico en C (D) de longitud
mínima y ui ∈ V(Ck) el vértice donde Ck cambia de color A a B; es decir, (ui−1, ui) es de color
A y (ui, ui+1) de color B.
Por el Lema 4.1, (ui+1, ui−1) < F(D) pero (ui−1, ui+1) ∈ F(D) y hay una (ui+1, ui−1)-trayectoria
dirigida monocromática de color G distinto de A y B. Sea P = (ui+1 = v0, v1, . . . , vt, vt+1 = ui−1)
con t ≥ 1, una de tales (ui+1, ui−1)-trayectorias monocromáticas de longitud mínima.
Caso 1) (ui−1, ui+1) no es de color G.
Por hipótesis la clase cromática G es cuasitransitiva por lo que a la subdigráfica inducida
por esta, llamemosla H podemos aplicarle el Corolario 3.1 dado que (ui−1, ui+1) < F(H) y como
P es de longitud mínima, existen vértices v1 y v2 en H tal que {v1, v2}∩ {ui−1, ui+1} = ∅ y cumplen
que (ui+1, v1, v2, ui−1) y (ui−1, v1, v2, ui+1) son trayectorias dirigidas monocromáticas en G.
Observemos que el ciclo de longitud 5, C = (ui, ui+1, v1, v2, ui−1, ui) es policromático, ya que
(ui, ui+1) es de color B, (ui+1, v1, v2, ui−1) de color G y (ui−1, ui) de color A (véase Figura 4.3).
19
Figura 4.3: El ciclo C claramente es policromático.
Por lo que si q = 5, tendríamos a C que no es cuasimonocromático. Así que q , 5, pues
C no es cuasimonocromático y para q ≥ 6 existiría al menos C que es policromático, lo cual
contradice la hipótesis (c). Por lo tanto q = 4.
Dado que C es cuasitransitivo en el borde [ui, v1] ∈ F(D).
Afirmación 1.1: (v1, ui) ∈ F(D) y es de color B.
Demostración de la afirmación 1.1:
Si (ui, v1) ∈ F(D), entonces como C1 = (ui, v1, v2, ui−1, ui) tiene longitud 4, debe ser cuasi-
monocromático por hipotésis. Ya que (v1, v2, ui−1) es de color G y (ui−1, ui) de color A, entonces
(ui, v1) es de color G. De esta manera se tiene la trayectoria monocromática (ui, v1, v2, ui−1),
por lo que (ui, ui−1) ∈ F(C (D)), contradiciendo la asimetría de Ck. Por lo tanto (v1, ui) ∈ F(D)
(véase Figura 4.4).
Figura 4.4: [ui, v1] ∈ F(D).
20
Observemos el triángulo dirigido (v1, ui, ui+1, v1). Ahora (v1, ui) es de color G ó B ya que
si fuera de cualquier otro color sería policromático y eso no puede pasar por la condición
(c). Si (v1, ui) es de color G, se formará la trayectoria (ui+1, v1, ui, ) de color G. Por lo que
(ui+1, ui) ∈ F(C (D)) y eso contradice que Ck sea asimétrico. Por lo que se concluye que
(v1, ui) ∈ F(D) y es color B.
Como {(v2, ui−1), (ui−1, ui)} ⊆ F(C), y dado que C es cuasitransitivo en el borde tenemos que
[ui, v2] ∈ F(D).
Afirmación 1.2: (ui, v2) ∈ F(D) y es de color A.
Demostración de la afirmación 1.2:
Si (v2, ui) ∈ F(D), dado que el ciclo C2 = (ui, ui+1, v1, v2, ui) es de longitud 4, (ui+1, v1, v2)
es de color G y (ui, ui+1) de color B, tenemos que (v2, ui) es de color G, pues los C4 son cuasi-
monocromáticos. Entonces tenemos la trayectoria monocromática (ui+1, v1, v2, ui) de color G lo
que implica que (ui+1, ui) ∈ F(C (D)), lo que nos lleva a una contradición con la asimetría de
Ck. Por lo tanto (ui, v2) ∈ F(D) (véase Figura 4.5).
Figura 4.5: [ui, v2] ∈ F(D).
Fijémonos en el triángulo (v2, ui−1, ui, v2). Por lo tanto (ui, v2) es de color G ó A. Si (ui, v2)
es de color G, por la trayectoria (ui, v2, ui−1) de color G, tendríamos que (ui, ui−1) ∈ F(C (D)) y
eso contradice que Ck sea asimétrico. Por lo tanto (ui, v2) ∈ F(D) y es de color A.
Ahora tomando en cuenta las dos afirmaciones 1.1 y 1.2 observemos que C∗ = (ui, v2, ui+1, v1, ui)
es un ciclo de longitud 4 y no es cuasimocromático, esto es una contradicción a la condición
(c). Así este caso no es posible (véase Figura 4.6).
21
Figura 4.6: C∗ es de longitud 4 y no es cuasimonocromático
Caso 2) (ui−1, ui+1) es de color G.
Recordemos que P = (ui+1 = vo, v1, v2, . . . , vt, vt+1 = ui−1) es una trayectoria dirigida mono-
cromática de longitud mínima (ℓ(P) = t + 1). Por la proposición 3.1, D[V(P)] es una digráfica
semicompleta de color G y se tiene que {(ui−1, v1), (vt, ui+1), (ui−1, v j), (v j, ui+1)} ⊆ F(D). con
2 ≤ j ≤ t − 1 y (vr, vs) ∈ F(D) para 1 ≤ s ≤ r − 2, s + 2 ≤ r ≤ t. Además tenemos que
(ui−1, ui+1) ∈ F(D) de color G.
Observemos que el ciclo C1 = (ui, ui+1, v1, v2, . . . , vt, ui−1, ui) es un ciclo policromático de
longitud ℓ(P) = t + 3 dado que (ui, ui+1) es de color B, la trayectoria (ui+1, v1, . . . , vt, ui−1) de
color G y (ui−1, ui) de color A. De tal manera que si q = t + 3, tenemos un ciclo de longitud q
que no es cuasimonocromático y si q > t + 3 tenemos un ciclo de longitud menor a q que es
policromático. En ambos casos se contradice la condición (c). Por lo tanto q ≤ t + 2, lo que
implica t ≥ q − 2 (véase Figura 4.7).
Figura 4.7: La longitud de C1 es t + 3.
Observación 3). Si (ui, v j) ∈ F(D) y es de color G, por la trayectoria (ui, v j, v j+1, . . . , vt, ui−1)
de color G, la flecha (ui, ui−1) ∈ F(C (D)). Si (v j, ui) ∈ F(D) y es de color G, por la trayectoria
(ui+1, v1, v2, . . . , v j, ui), la flecha (ui+1, ui) ∈ F(C (D)). En ambos casos se contradice la asimetría
22
de Ck. Por lo tanto sí [ui, v j] ∈ F(D), entonces [ui, v j] no es de color G para toda j ∈ {1, 2, . . . , t}
(véase Figura 4.8).
Figura 4.8: Aqui se pueden ver los casos de la observación 3.
Por hipótesis todos los ciclos son cuasitransitivos en el borde en particular C1, por lo que
tenemos adyacencias entre ui y los v j con j ∈ {1, 2, . . . , t}, por lo que existen las siguiente posi-
bilidades:
1) (ui, v j) ∈ F(D) para toda j ∈ {1, 2, . . . , t}.
Supongamos que no existe α ∈ {1, 2, ..., t} tal que (vα, ui) ∈ F(D). Como C1 es cuasitran-
sitivo en el borde, tenemos que (ui, v1) ∈ F(D). Obsérvese que si (ui, v j) ∈ F(D), entonces
por la cuasitransitividad en el borde del ciclo H = (ui, v j, v j+1, ..., vt, ui−1, ui), se tiene que
[ui, v j+1] ∈ F(D), es decir, (ui, v j+1) ∈ F(D) por nuestra suposición. De esta manera podemos
asegurar que (ui, v2) ∈ F(D) y de manera análoga (ui, v j) ∈ F(D) para toda j ∈ {1, 2, . . . , t}.
Tomemos el ciclo C′ = (ui, vt−(q−3), vt−(q−2), . . . , vt, ui−1, ui) que es un ciclo de longitud q que
no es cuasimonocromático, ya que (ui, vt−(q−3)) es de color distinto a G por la observación 3,
la trayectoria (vt−(q−3), vt−(q−2), . . . , vt, ui−1) es de color G y (ui−1, ui) es de color A. Lo cual con-
tradice la hipótesis (c). Por lo que debe existir α ∈ {1, 2, . . . , t} tal que (vα, ui) ∈ F(D) (véase
Figura 4.9).
Figura 4.9: Representacion del ciclo C′.
23
2) (v j, ui) ∈ F(D) para toda j ∈ {1, 2, . . . , t},
Supongamos que no existe β ∈ {1, 2, . . . , t} tal que (ui, vβ) ∈ F(D) por nuestra supo-
sición de este caso. Como C1 es cuasitransitivo en el borde, tenemos que (vt, ui) ∈ F(D).
Obsérvese que si (v j, ui) ∈ F(D), entonces por la cuasitransitividad en el borde del ciclo
H′ = (ui, ui+1, v1, v2, . . . , v j−1, v j, ui) se tiene que [ui, v j−1] ∈ F(D), es decir; (v j−1, ui) ∈ F(D)
por nuestra suposición. De esta manera podemos asegurar (vt−1, ui) ∈ F(D) y de manera simi-
lar (v j, ui) ∈ F(D) para toda j ∈ {1, 2, . . . , t}.
Figura 4.10: Representación del ciclo C′′
Tomemos C′′ = (ui, ui+1, v1, v2, . . . , vq−2, ui) que es un ciclo de longitud q y que no es cuasi-
monocromático, ya que (ui, ui+1) es de color B, la trayectoria (ui+1, v1, . . . , vq−2) es de color G y
(vq−2, ui) es de color distinto a G, por la observación 3. Por lo que debe existir β ∈ {1, 2, .., t} tal
que (ui, vβ) ∈ F(D) (véase Figura 4.10).
3) Tomando en cuenta los dos incisos anteriores se tiene la posibilidad de que existan
{(ui, vα), (vβ, ui)} ⊆ F(D), para alguna {α, β ⊆ {1, 2, . . . , t} por lo que podemos definir a:
α∗ = mín{ j ∈ {1, 2, . . . , t} : (v j, ui) ∈ F(D)}, β∗ = máx{ j ∈ {1, 2, . . . , t} : (ui, v j) ∈ F(D)}.
Observación 4). Para toda j < α∗ se tiene que (ui, v j) ∈ F(D) y para toda j > β∗ se tiene
que (v j, ui) ∈ F(D).
Demostración de la obsevación 4: Claramente si α∗ = 1, tenemos que es cierto. Si α∗ > 1,
recordemos que [ui, v1] ∈ F(D), así (ui, v1) ∈ F(D); por lo tanto [ui, v2] ∈ F(D). Si 2 , α∗
entonces (ui, v2) ∈ F(D) lo que implica que [ui, v3] ∈ F(D). Y continuando así tenemos que
para toda j ∈ {1, 2, . . . , (α∗ − 1)} se tiene que (ui, v j) ∈ F(D).
Si β∗ = t se cumple por vacuidad. Para β∗ < t sabemos que [ui, vt] ∈ F(D) así que
(vt, ui) ∈ F(D) lo que implica que [ui, vt−1] ∈ F(D). Si β∗ , t−1, entonces [ui, vt−2] ∈ F(D), tene-
mos que (vt−2, ui) ∈ F(D) por lo tanto [ui, vt−3] ∈ F(D). Siguiendo así se tiene que (v j, ui) ∈ F(D)
24
para toda j ∈ {(β∗ + 1), . . . , t}.
Afirmamos que α∗ < q − 2. Si α∗ ≥ q − 2, tomemos el ciclo (ui, vα∗−(q−2), vα∗−(q−3), . . . , vα∗ , ui)
de longitud q que no es cuasimonocromático. Recordemos que (ui, vα∗−(q−2)) y (vα∗ , ui) no son de
color G, por la observación 3. Por lo tanto α∗ < q − 2 (véase Figura 4.11).
Figura 4.11: Aqui se puede observar que pasa con α∗ ≥ q − 2.
Afirmamos que β∗ > t−(q−3). Si β∗ = t−q+3 observemos el ciclo (ui, vβ∗ , . . . , vt, ui−1, ui), de
longitud q que no es cuasimonocromático, ya que (ui, vβ∗) no es de color G por la observación
3 y (ui−1, ui) es de color A (véase Figura 4.12).
Figura 4.12: Para β∗ = t − q + 3 tenemos este ciclo.
Si β∗ < t − q + 3
se tiene que −β∗ > −t + q − 3
de tal manera que t > β∗ + q − 3
por lo tanto t ≥ β∗ + q − 2
25
Sea h = β∗+q−2. Fijémonos en C′′′ = (ui, vβ∗ , vβ∗+1, . . . , vh, ui) el cual es un ciclo de longitud
q no cuasimocromático dado que (vh, ui) y (ui, vβ∗) son de color distinto a G, por la obsrvación
3. Por lo tanto β∗ > t − (q − 3) (véase Figura 4.13).
Figura 4.13: Representacion del ciclo C′′′ para β∗ < t − q + 3.
Por lo que tenemos los siguientes casos:
I) Si β∗ ≥ α∗
a) Si β∗ −α∗ ≥ q− 2 tenemos el ciclo: (ui, vβ∗ , vβ∗−(q−3), vβ∗−(q−2), . . . , vβ∗−1, vα∗ , ui) de longitud
q el cual no es cuasimonocromático. Recordemos que (ui, vβ∗) y (vα∗ , ui) son de color distinto a
G, por la observacion 3 (vé aseFigura 4.14).
Figura 4.14: Representación del ciclo propuesto en el inciso a.
b) Si β∗ − α∗ < q − 3 , entonces existen δ > β∗ y γ < α∗, por la oobservación 4, tales
26
que δ − γ = q − 2. Por lo que tenemos el ciclo (ui, vγ, vγ+1, . . . , vα∗ , . . . , , vβ∗ , vβ∗+1, . . . , vδ, ui) de
longitud q no cuasimonocromático, ya que (ui, vγ) y (vδ, ui) son de color distinto a G, por la
observación 3 (veasé Figura 4.15).
Figura 4.15: Representacion del ciclo que se da en el inciso b.
c) Si β∗ − α∗ = q − 3. Veamos los siguientes casos: Para β∗ > α∗ + 2, observemos el ciclo
(ui, vβ∗ , vα∗+1, P, vβ∗−1, vα∗−1, vα∗ , ui) de longitud q que no es cuasimonocromático (véase Figura
4.16)
Figura 4.16: Si β∗ > α∗ + 2.
Si β∗ = α∗+2, esto implica que q = 5. Por lo que tomemos el ciclo (ui, vβ∗ , vβ∗+1, vα∗−1, vα∗ , ui)
que es de longitud q y no es cuasimonocromático.(véase Figura 4.17
27
Figura 4.17: Si β∗ = α∗ + 2.
Por último si β∗ = α∗ + 1, se tiene que q = 4. Así tenemos el ciclo (ui, vβ∗ , vα∗−1, vα∗ , ui) que
tiene longitud 4 y no es cuasimonocromatico. (véase Figura 4.18)
Figura 4.18: Para β∗ = α∗ + 1.
Con todo lo demostrado en los incisos anteriores podemos concluir que este caso no es
posible.
II) β∗ < α∗
Como (vβ∗ , ui) es la última flecha que va hacía ui y (ui, vα∗) es la primera que regresa a ui
tenemos que β∗ = α∗−1. Como t ≥ q−2 y α∗ < q−2, existen δ > α∗ y γ < β∗, por la observación
4 tales que δ − γ = q − 2. Fijémonos en el ciclo (ui, vγ, . . . , vβ∗ , vα∗ , . . . , vδ, ui) de longitud q que
no es cuasimonocromático, ya que (ui, vγ) y (ui, vδ) son de color distinto a G (véase Figura 4.19).
28
Figura 4.19: Si β∗ < α∗.
Tomando en cuenta los dos casos anteriores tenemos que Ck tiene al menos una flecha simé-
trica lo que implica que C (D) posee núcleo por 3.2. Con lo que se concluye que D tiene núcleo
por t.d.m.
A continuación se presenta un teorema para digráficas asimétricas, pero antes de llegar a ese
resultado necesitamos probar la siguiente proposición que nos ayudara mucho.
Proposición 4.1. Sea D una digráfica asimétrica m-coloreada tal que:
a) cada clase cromática es cuasitransitiva y
b) D no contiene C3 dirigidos policromáticos.
Si (u, v) ∈ F(D) y es asimétrica en C (D), entonces no existe C3 en D que contenga a (u, v).
Demostración 4.5. Procedamos por contradicción. Supongamos que (u, v) ∈ F(D), es asimé-
trica en C (D) y que existe un ciclo dirigido C = (u, v,w, u) en D.
Como D no contiene C3 policromáticos en C, dos de sus flechas son del mismo color. Ob-
servemos que (v,w) y (w, u) son de color distinto ya que no existen (v, u)-trayectorias mono-
cromáticas en D, por la asimétria de (u, v) en C (D). Sean (u, v) y (v,w) las flechas del mismo
color, digamos A.
Como cada clase cromática es cuasitransitiva, tenemos que [u,w] ∈ F(D) y debe ser de
color A. Pero por ser D una digráfica asimétrica (w, u) ∈ F(D). De tal manera, que tenemos
la trayectoria (v,w, u) monocromática, por lo tanto (v, u) ∈ F(C (D)) contradiciendo que sea
29
asimetríca en C (D).
Con lo que concluimos que no existe C3 en D que contenga a (u, v).
El siguiente teorema nos ayudará a reconocer cuándo una digráfica asimétrica tiene núcleo.
Teorema 4.3. Sea D una digráfica asimétrica m-coloreada tal que:
a) cada clase cromática es cuasitransitiva;
b) cada ciclo induce una digráfica cuasitransitiva, y
c) D no contiene C3 policromáticos.
Entonces D tiene núcleo por trayectorias dirigidas monocromáticas.
Demostración 4.6. Recordemos que D tiene núcleo por trayectorias dirigidas monocromáti-
cas, si C (D) tiene núcleo. Por lo que demostraremos que para todo Ck en C (D), Ck tiene al
menos una flecha simétrica.
Procedamos por contradición. Supongamos que existe Ck = (u0, u1, . . . , uk−1, u0) un ciclo
dirigido asimétrico en C (D). Por el lema 3.1, Ck es un ciclo asimétrico en D. Por hipótesis, Ck
induce una digráfica cuasitransitiva en D, ahora se tiene que {(u0, u1), (u1, u2) ⊆ F(Ck) por lo
tanto existe [u2, u0] ∈ F(D). Haciendo uso de la proposición 4.1 tenemos que no existe un C3
en D que contenga a (u2, u0). de tal manera que (u0, u2) ∈ F(Ck).
Dado que {(u0, u2), (u2, u3)} ⊆ F(Ck) y como Ck induce una digráfica cuasitransitiva en D,
se tiene que [u0, u3] ∈ F(Ck) y por la proposición 4.1 se concluye que (u0, u3)} ∈ F(Ck). Conti-
nuando de manera similar obtenemos que (u0, u j) ∈ F(D) para cada j ⊆ {2, 3, . . . , k − 2}
Pero en D tenemos a (uo, uk−2, uk−1, u0) que es un C3, lo cual contradice que no existe en D
un C3 que contenga alguna de las flechas del ciclo, ya que estas flechas son simétricas por la
proposición 4.1 (véase Figura 4.20).
Por lo tanto, todo Ck ∈ C (D) tiene al menos una flecha simétrica. Quedando demostrado
que C (D) posee núcleo. Con lo que se concluye que D tiene núcleo por t.d.m.
30
Figura 4.20: El ciclo Ck del teorema 4.3.
El siguiente corolario resuelve en gran medida el problema de encontrar núcleos para una
clase particular de digráficas m-coloreadas como son los torneos donde todas sus clases cromá-
ticas son cuasitransitivas.
Corolario 4.2. Sea T un torneo m-coloreado tal que:
a) cada clase cromática es cuasitransitiva,
b) T no contiene C3 policromáticos.
Entonces T tiene núcleo por trayectorias dirigidas monocromáticas.
Demostración 4.7. Por definición un torneo es una digráfica semicompleta con una sola orien-
tacion en cada flecha, por lo que en particular cada ciclo de T induce una digráfica cuasitran-
sitiva. Así T cumple la única hipótesis que nos faltaba del teorema 4.3. Con lo que se concluye
que T tiene núcleo por t.d.m.
31
Capítulo 5
Conclusiones
En la introducción de este trabajo se abordó el problema de encontrar condiciones sufi-
cientes para responder a la pregunta, ¿Si T es un torneo m-coloreado, sin triángulos dirigidos
policromáticos entonces T tiene núcleo por trayectorias dirigidas monocromáticas ?. Pues bien
tanto el corolario 4.1 y el corolario 4.2 nos dan condiciones suficientes para encontrar núcleo en
torneos m-coloreados sin triángulos policromáticos, pidiéndoles que sus clases cromáticas sean
cuasitransitivas, por lo que se da una respuesta parcial a la pregunta planteada, dejando aún una
gran parte sin respuesta de tal manera que da un montivo para seguir investigando en busca de
más condiciones.
32
Capítulo 6
Bibliografía
33
Bibliografía
[1] J. Bang-Jensen and J. Huang, Quasi-transitive Digraphs, J. Graph Theory 20, No.2 (1985),
141-161.
[2] P. Duchet, Graphes noyau-parfaits, Annals of Discrete Math. 9 (1980), 93-101.
[3] H. Galeana-Sánchez, B.Llano and J.J. Montellano-Ballesteros, Kernels by monochroma-
tic directed paths in m-colored digraphs with quasi-transitive chromatic classes, Ars Com-
bin.106 (2012), 461-471.
[4] H. Galeana-Sánchez, B. Llano and J. J. Montellano-Ballesteros, Absorbent sets and ker-
nels by monochromatic directed paths in m-colored tournaments, Australas. J. Combin. 40
(2008), 197-209.
[5] H. Galeana-Sánchez and R. Rojas-Monroy, A counterexample to a conjecture on edgecolo-
red tournaments, Discrete Math. 282 (2004), 275-276.
[6] J. von Neumann and O. Morgenstern, Theory of games and economic behaviour, Princeton
University Press, 1944.
[7] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-colored digraphs, J.
Combin. Theory Ser. B 33 (1982), 271-275.
[8] M. G. Shen, On monochromatic paths in m-colored tournaments, J. Combin. Theory Ser. B
45 (1988), 108-111
34