UNIVERSIDAD NACIONAL AUTÓNOMA  
                                 DE MÉXICO 
 
 FACULTAD DE CIENCIAS 
 
 
k-árboles m-dominantes en gráficas 
n-conexas 
 
 
 
 
 
 
 
 
 
T               E               S                I               S 
 
 
 QUE  PARA  OBTENER  EL  TÍTULO  DE:  
 MATEMÁTICO  
 P       R       E       S       E       N       T       A :  
  
Daniel Scognamiglio Moreno 
 
 
 
 
 
 
 
 
 
DIRECTOR DE TESIS:  
Mat. Laura Pastrana Ramírez 
Ciudad Universitaria, Cd. Mx., 2019 
 
 
 
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. 
 
  
 
2
Datos del Alumno
Apellido paterno: Scognamiglio
Apellido materno: Moreno
Nombre(s): Daniel
Teléfono: 0445536751754
Universidad: Universidad Nacional Autónoma
de México
Facultad: Facultad de Ciencias
Número de cuenta: 412049567
Datos del tutor
Grado: Mat.
Apellido paterno: Pastrana
Apellido materno: Ramírez
Nombre(s): Laura
Datos del sidnodal 1
Grado: Dra.
Apellido paterno: Galeana
Apellido materno: Sánchez
Nombre(s): Hortensia
Datos del sinodal 2
Gado Dr.
Apellido paterno: Rivera
Apellido Materno: Campo
Nombre(s): Eduardo
Datos del sinodal 3
Grado: Mat.
Apellido paterno: Pastrana
Apellido materno: Ramírez
Nombre(s): Laura
Datos del sinodal 4
Grado: Dra.
Apellido paterno: Sánchez
Apellido materno: López
Nombre(s): María del Rocío
3
Datos del sinodal 5
Grado: M. en C.
Apellido paterno: Benítez
Apellido materno: Bobadilla
Nombre(s): Germán
Datos de la tesis
Título: k-árboles m-dominantes en gráficas n-conexas.
Número de páginas: 140 p.
Año: 2019
Agradecimientos
A mi asesora de tesis Laura Pastrana Ramírez.
A mis sinodales Dra. Hortensia Galeana Sánchez, Dr. Eduardo Rivera Campo,
Dra. María del Rocío Sánchez López y M. en C. Gremán Benítez Bobadilla por
sus comentarios y sugerencias para la corrección de esta tesis.
A mi compañero y amigo Jorge Fernando Ibarra Corona (Pero bueno FolagoRRR).
A las amistades con las que puedo compartir este logro.
Y por último; a mis padres por su apoyo constante a lo largo de mi formación.
4
Índice general
Bibliografía 1
1. Conceptos elementales y primeros resultados 10
1.1. Gráfica: definición y ejemplos . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Grado y vecindad de un vértice . . . . . . . . . . . . . . . . . . . . . . 13
1.3. Algunos tipos de gráficas . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4. Subgráficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5. Caminos en gráficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.6. Gráficas conexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7. Algunas operaciones en gráficas . . . . . . . . . . . . . . . . . . . . . . 23
1.8. Vértices de corte, aristas de corte y bloques . . . . . . . . . . . . . . . 26
1.9. Árboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.10. Gráficas hamiltonianas . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.11. Conexidad puntual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.12. Independencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.13. Teorema Chvátal-Erdös . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.14. Dominación en gráficas . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.15. Digráficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2. Árboles generadores con grados acotados 53
2.1. Lema de apoyo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.2. Árboles generadores con grado acotado . . . . . . . . . . . . . . . . . . 56
3. k-árboles m-dominantes en gráficas 69
3.1. Definiciones y primeros resultados . . . . . . . . . . . . . . . . . . . . . 70
3.2. k-árboles m-dominantes en gráficas . . . . . . . . . . . . . . . . . . . . 74
3.3. Aplicación sobre una red de distribución de agua potable . . . . . . . . 118
Bibliografía 138
5
Introducción
La teoría de gráficas es la rama de las matemáticas que tiene sus fundamen-
tos en las matemáticas discretas. Esta requiere herramientas de diversas
áreas, como combinatoria, álgebra, probabilidad, geometría de polígonos,
aritmética y topología. Actualmente ha tenido mayor influencia en el cam-
po de la informática, las ciencias de la computación y telecomunicaciones;
debido a la gran cantidad de aplicaciones en la optimización de recorridos,
procesos, flujos, algoritmos de búsquedas, entre otros.
Por ejemplo, en la Figura 1, podemos observar como la red ferroviaria de
España de 1872 puede ser modelada por una gráfica; en la cual las ciudades
son representadas por vértices y las vías férreas por aristas. Observemos
que entre todo par de vértices de la gráfica existe una única trayectoria; lo
que nos indica que la gráfica es conexa. A estas gráficas se les conoce como
árboles.
Figura 1: Red ferroviaria de España en 1872
6
ÍNDICE GENERAL 7
Al conectar todas las ciudades de España con una única trayectoria, se utiliza
el mínimo número de aristas, en esto radica la importancia del estudio de los
árboles. Un árbol es generador de una gráfica conexa G, si este es subgráfica
de G y contiene a todos los vértices de G. Podemos decir que el árbol que
aparece en la Figura 1; es un árbol generador de la gráfica conexa de las
ciudades principales de España. Hallar un árbol generador en una gráfica
conexa ha sido un problema de estudio de mucha relevancia para la teoría
de gráficas. Hoy en día sabemos que toda gráfica conexa G tiene un árbol
generador.
Una clase especial de árboles son los k-árboles, con k un entero mayor o
igual que 2, los cuales son aquellos árboles que tienen grado máximo a lo
más igual a k. Lo natural sería preguntarse si toda gráfica tiene un k-árbol
generador.
El primer resultado que encuentra un 2-árbol generador aparece en 1971;
cuando Chvátal y Erdös dan el resultado siguiente: Sean n ≥ 1 un entero y
G una gráfica n-conexa. Si α(G) ≤ n + 1, entonces G tiene una trayectoria
hamiltoniana, donde α(G) es el número de independencia; el cual cumple
que α(G) = máx{|S| : S es un conjunto independiente}. Este teorema aparece
en el artículo “A note on hamiltonian circuits” [9]. Observemos que una
trayectoria hamiltoniana es un 2-árbol generador.
Posteriormente M. Las Vergnas se preguntó qué condiciones debe tener una
gráfica n-conexa G para que tenga un árbol generador con al menos l vértices
finales [15].
En 1979; S. Win en el artículo “On a conjeture of Las Vergnas concentring
certain spanning trees in graphs” [15] plantea el resultado siguiente como
solución a la pregunta anterior: Sea G una gráfica n-conexa. Si α(G) ≤
n + l − 1, entonces G tiene un árbol generador de G con l-hojas.
Más adelante en 1988 Víctor Neumann Lara y Eduardo Rivera Campo pre-
sentan los siguientes resultados:
Sean G una gráfica n-conexa con número de independencia α(G), s y c dos enteros
tales que 3 ≤ s y 0 ≤ c ≤ k. Si α(G) ≤ 1 + k(s − 1) + c, entonces G tiene un árbol
generador con grado máximo a lo más s + 1 que contiene a lo más c vértices de
grado s + 1.
8 ÍNDICE GENERAL
Sea G una gráfica n-conexa con número de independencia α(G). Si
α(G) ≤ 1 + ns para algún entero positivo s, entonces G tiene un árbol generador
con grado máximo a lo más s + 1.
Estos teoremas son una generalización al enunciado de Chvátal y Erdös,
que permiten encontrar un (s + 1)-árbol generador en una gráfica n-conexa
con un número de independencia dado. Dichos resultados se encuentra en
el artículo “Spanning tree with bounded degrees” [13].
Por otro lado, además de tener k-árboles generadores, también contamos
con los k-árboles m-dominantes; un k-árbol T m-domina a G, si cumple que
T es subgráfica de G y para todo v ∈ V (G) se tiene que dG(v, T ) ≤ m.
Broersma postuló que en una gráfica n-conexa con invariante
α2(m+1)(G) ≤ n + 1
contiene una trayectoria P que m-domina a G [5]. Observemos que P es un
2-árbol que m-domina a G. Esto también resulta ser una generalización al
resultado propuesto por Chvátal y Erdös [9], pues si se da el caso para m = 0
se halla un 2-árbol generador de G.
Luego en 2014, Mikio Kano, Kenta Ozeki, Masao Tsugaki y Guiying Yan
averiguaron que se puede hallar un k-árbol m-dominante en una gráfica n-
conexa con invariante α2(m+1)(G) ≤ (k − 1)n + 1. Este resultado aparece en el
artículo “m-dominanting k-trees of graphs” [12] y es presentado como una
generalización a los teoremas propuestos por Broersma, V. Neumann Lara
y E. Rivera Campo.
En esta tesis nos centraremos en hacer el estudio de los resultados propues-
tos por Chvátal, Erdös, V. Neumann Lara, E. Rivera Campo, Mikio Kano,
Kenta Ozeki, Masao Tsugaki y Guiying Yan.
A lo largo del primer capítulo nos enfocaremos en establecer las definiciones
y teoremas que darán sustento al estudio de los k-árboles. A la par de esto
se hará la revisión del resultado que aparece en el artículo “A note on
hamiltonian circuits” [9], donde se obtiene un 2-árbol generador.
En el segundo capítulo se estudiará al (s + 1)-árbol a través del artículo
“Spanning tree with bounded degrees” [13].
ÍNDICE GENERAL 9
En el tercer capítulo se dará la demostración del teorema para encontrar
un k-árbol m-dominante en una gráfica n-conexa que aparece en el artículo
“m-dominanting k-trees of graphs” [12]. Posteriormente proponemos un
algoritmo para encontrar un k-árbol m-dominante, en una gráfica que cumpla
las condiciones del teorema probado en este capítulo; deducido a partir de
dicha demostración. Por último se da una posible solución al problema de
distribución de agua en una red pequeña, usando k-árboles m-dominantes.
Capítulo 1
Conceptos elementales y primeros
resultados
Comenzaremos con un poco de historia para visualizar como se produjo el
primer acercamiento a lo que hoy se conoce como teoría de gráficas. De igual
manera a lo largo de este capítulo sentaremos las definiciones y resultados
que darán sustento a los objetivos de estudio de este trabajo.
1.1. Gráfica: definición y ejemplos
En el año de 1736, se le planteó al matemático Leonhard Euler el "Proble-
ma de los puentes de Königsberg". El cual consistía en encontrar un paseo
dominical, que comenzara y finalizara en el mismo sitio, después de recorrer
los siete puentes de la ciudad, sin pasar dos o más veces por ninguno de
ellos. En la Figura 1.1 podemos observar como se ve la ciudad dividida en
islas y los puentes entre los segmentos de tierra.
Figura 1.1: Dibujo de la ciudad de Königsberg
10
1.1. GRÁFICA: DEFINICIÓN Y EJEMPLOS 11
Euler realizó un modelo matemático del problema, en el cual considero como
puntos a las partes de tierra y como líneas a los puentes entre los puntos, lo
que derivó en la representación de la Figura 1.2.
Figura 1.2: Representación propuesta por Euler
Observó que cuando llegamos a uno de los puntos por un puente, solo se
puede salir del punto a través de otro puente. En otras palabras, el número
de veces que entras en un punto es igual al número de veces que sales de
él; es decir, que deben llegar un número par de puentes a cada punto para
que cada puente sea atravesado exactamente una vez. Sin embargo, cuatro
de los puntos en el problema son tocados por un número impar de puentes,
por lo que, el no repetir puentes es imposible.
El trabajo de Euler, el cual fue publicado el 26 de agosto de 1736, es consi-
derado el primero en el campo de la teoría de gráficas.
Este modelo realizado por Euler se conoce como gráfica, por lo que podemos
ahora dar nuestra primera definición.
Definición. Una gráfica G es un par ordenado (V (G), A(G)) donde V (G) es un
conjunto finito y no vacío de objetos, al que llamaremos conjunto de vértices
de G, y A(G) es un conjunto de pares no ordenados de vértices distintos, al
que llamaremos conjunto de aristas de G.
12 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Diremos que una gráfica es simple si en ella no hay aristas múltiples (observe
que en la Figura 1.2 entre los vértices A y B hay una arista múltiple) entre
dos vértices y no tiene lazos. Como nota señalaremos que para este trabajo
trabajaremos con gráficas simples.
Dada una gráfica G, la cardinalidad de V (G) es el orden de G y la cardinalidad
de A(G) es el tamaño de G. El orden de cualquier gráfica es al menos uno.
Dada una gráfica G y dos vértices u y v en G, si {u, v} en A(G) diremos que:
u y v son vértices adyacentes, u y v son los extremos de la arista {u, v}; la
arista {u, v} incide en u e incide en v. La forma de denotar la arista {u, v}
de una gráfica será uv.
Definición. Sean G una gráfica, u un vértice en G y U un subconjunto de
vértices de G tal que u /∈ U . Decimos que u es adyacente a U si u es adyacente
a uno o más vértices de U , por lo que podemos decir que existe al menos
una uU-arista.
Sean U y B dos subconjuntos de vértices de G, decimos que existe una UB-
arista si tenemos un vértice u en U tal que existe al menos una uB-arista.
Ejemplo. Sea G = (V (G), A(G)) una gráfica, con V (G) = {x1, x2, x3, x4, x5} y
A(G) = {f = x1x2, g = x1x3, i = x2x4 , j = x3x4, h = x3x5}.
La representación geométrica de una gráfica resulta de dibujar en el plano
puntos asociados a los vértices y líneas entre dos puntos si los vértices corres-
pondientes son adyacentes, la Figura 1.3 representa la gráfica del ejemplo
anterior.
Figura 1.3: Ejemplo de una gráfica
1.2. GRADO Y VECINDAD DE UN VÉRTICE 13
Cuando una gráfica G consiste de un sólo vértice, se dice que G es trivial.
Las representaciones que aparecen en la Figura 1.4 son algunos ejemplos de
gráficas.
Figura 1.4: Diferentes gráficas
1.2. Grado y vecindad de un vértice
Definición. Sean G una gráfica y v un vértice de G, diremos que el grado de
v es el número de aristas que inciden en él o también lo podemos ver como
el número de vértices adyacentes a él. Lo denotaremos por δG (v).
Notemos que podemos tener en una gráfica vértices con grado cero; es decir,
no tienen aristas que incidan en ellos.
Definición. El grado máximo ∆(G) de una gráfica G es:
∆(G) = máx{δG(v)| v ∈ V (G)}.
Definición. El grado mínimo δ(G) de un gráfica G es:
δ(G) = mı́n{δG(v)| v ∈ V (G)}.
Definición. Dada una gráfica G y un vértice v de G, al conjunto de vértices
adyacentes a v se le llama la vecindad de v en G y se denota por NG(v).
Notemos que en una gráfica G para todo vértice v de G, se cumple que:
δG(v) = |NG(v)|.
14 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Veamos el primer teorema de esta tesis.
Teorema 1.2.1. Si G es una gráfica de tamaño q, entonces se cumple que
∑
v∈V (G)
δG(v) = 2q.
Demostración. Sea G una gráfica de orden p y tamaño q. Haremos la demostración por
inducción sobre el tamaño de G. Supongamos que V (G) = {v1, v2, ..., vp}.
Base. Cuando q = 0, G no tendrá ninguna arista. Por otro lado, se cumple que para
toda i en {1, 2, ..., p} δG(vi) = 0. Por lo que
∑
vi∈V (G)
δG(vi) = 0.
Cuando q = 1, G tiene exactamente una arista. Por lo tanto, existirán exactamente
dos vértices cuyo grado sea igual a uno y el resto tendrá grado cero. Por lo tanto,
tenemos que ∑
vi∈V (G)
δG(vi) = 1 + 1 = 2(1) = 2q.
Hipótesis de inducción. Sean p′ y q′ dos números enteros positivos, tales que
1 ≤ q′ ≤ q y supongamos que para toda gráfica G′ de orden p′ y tamaño q′ se cumple
que para toda i en {1, 2, ..., p′}
∑
vi∈V (G′)
δG′(vi) = 2q′.
Paso inductivo. Consideremos una gráfica G de orden p y tamaño q. Ya que q > 1
tomemos una arista e en A(G). Sin pérdida de generalidad, podemos suponer que
e = v1v2. Ahora construiremos una nueva gráfica G′ que satisfaga la hipótesis de induc-
ción con V (G′) = V (G) y A(G′) = A(G) \ e.
Notemos que el orden de G′ es p y su tamaño es q′ = q − 1. Además tenemos lo
siguiente
δG′(v1) = δG(v1) − 1,
δG′(v2) = δG(v2) − 1,
δG′(vi) = δG(vi) para toda i en {3, 4, ..., p}.
Por hipótesis de inducción y al sustituir las equivalencias previas, tenemos que
∑
vi∈V (G′)
δG′(vi) = 2q′,
(δG(v1) − 1) + (δG(v2) − 1) +
p∑
i=3
δG(vi) = 2q′,
1.3. ALGUNOS TIPOS DE GRÁFICAS 15
δG(v1) + δG(v2) +
p∑
i=3
δG(vi) = 2q′ + 2,
δG(v1) + δG(v2) +
p∑
i=3
δG(vi) = 2(q′ + 1),
p∑
i=1
δG(vi) = 2q.
1.3. Algunos tipos de gráficas
En esta sección definiremos algunos tipos de gráficas con las que trabajare-
mos en esta tesis.
Definición. Decimos que una gráfica G es isomorfa a una gráfica H si existe
f : V (G) → V (H) una función biyectiva con regla de correspondencia f(v) = v′,
tal que xy ∈ A(G) si y solo si x′y′ en A(H). Y se denota como G ∼= H.
Figura 1.5: Gráficas isomorfas
Definición. Sea G una gráfica. Una partición de V (G), está dada por
{V1, V2, · · · , Vn} donde cada Vi es un subconjunto de vértices de G, tal que:
Para cada i ∈ {1, 2, . . . , n} tenemos que Vi ⊆ V (G) y Vi 6= ∅.
Para cada par i 6= j con i, j ∈ {1, 2, . . . , n}, se cumple Vi
⋂
Vj = ∅.
Para i ∈ {1, 2, . . . , n} tenemos que
⋃n
i V i = V (G).
16 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Definición. Diremos que G es una gráfica bipartita si existe una partición del
conjunto de vértices en dos conjuntos de vértices I y U , tal que las aristas
de G tienen un extemo en el conjuto de I y otro extemo en el conjunto U .
Definición. Diremos que G es una gráfica k-regular si todos los vértices de
G tienen grado k.
Si cada par de vértices tiene un arista entre ellos tenemos la siguiente gráfica:
Definición. Una gráfica G se dice que es completa si cualquier par de sus
vértices son adyacentes; es decir, para todo v en V (G) se tiene que δ(v) = p−1.
Se denota por Kn donde n es el número de vértices de G.
Las gráficas de la Figura 1.6 son gráficas completas que a su vez son también
gráficas (p − 1)-regulares.
Figura 1.6: Gráficas completas
1.4. Subgráficas
De manera intuitiva, una subgráfica es una gráfica que vive dentro de otra
gráfica. Así, tenemos la siguiente definición.
Definición. Dada una gráfica G, diremos que H es una subgráfica de G si H
cumple que V (H) ⊆ V (G) y A(H) ⊆ A(G). Lo denotamos como H ≤ G.
Note que toda gráfica G es subgráfica de sí misma.
1.5. CAMINOS EN GRÁFICAS 17
Si H es subgráfica de G, pero V (H) ⊂ V (G), decimos que H es una subgráfica
propia de G.
Adicionalmente, tenemos dos clases especiales de subgráficas con las que
trabajaremos.
Definición. Dada una gráfica G y S un subconjunto de los vértices de G,
la subgráfica inducida por S en G, denotada como G[S] o 〈S〉G, tiene por
conjunto de vértices a S y dos vértices en G[S] son adyacentes si y solo si
son adyacentes en G.
Definición. Sea G una gráfica. H es una subgráfica generadora de G si y solo
si V (H) = V (G).
A continuación se muestra un ejemplo de una gráfica G (Figura 1.7) y una
subgráfica generadora de G.
Figura 1.7: Gráfica G y H su subgráfica greneradora
1.5. Caminos en gráficas
Definición. Sea G una gráfica. Un camino: C = (x0, x1, · · · , xn−1, xn), es una
sucesión de vértices de G que cumple que ei = xixi+1 en A(G) con 0 ≤ i ≤ n−1.
Definimos su longitud como n y se denota por l(C) = n. Llamaremos un x0xn-
camino a un camino que inicia en x0 y finaliza en xn.
18 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Definición. Sea G una gráfica, para todo par de vértices distintos de G,
decimos que la distancia en G de x a y es igual a la mínima longitud de los
xy-caminos. Lo denotamos como dG(x, y).
Figura 1.8: dG(x, y) = 2
Para dos subconjuntos de vértices X y Y de G, la distancia de X a Y se
define como sigue:
dG(X, Y ) = mín{dG(x, y) : x ∈ X y y ∈ Y }.
Si tenemos que dG(X, Y ) = 0, entonces quiere decir X ∩ Y = ∅.
Definición. Sea G una gráfica, un camino C = (x0, x1, . . . , xn−1, x0) es cerrado
si el vértice inicial y el vértice final son iguales.
Definición. Sea G una gráfica, un camino en el que no se repiten aristas se
llama paseo.
Definición. Sea G una gráfica, un camino en el que no se repiten vérti-
ces se llama trayectoria. Denotaremos a las trayectorias como sigue P =
(x0, x1, x2, . . . , xm), diremos que P es una (x0, xm)-trayectoria. Una subtrayec-
toria de P que va de xi a xj, como P ′ = (xi, P, xj); es decir, (xi, P, xj) =
(xi, xi+1, ..., xj−1, xj).
Si P = (u = x1, x2, ..., xn = v) es una (u, v)-trayectoria, entonces P −1 = (v =
xn, xn−1, ..., x2, x1 = u) es la (v, u)-trayectoria; es decir, que se recorre la tra-
yectoria P en sentido contrario.
1.5. CAMINOS EN GRÁFICAS 19
Decimos que dos (u, v)-trayectorias T y Y son internamente ajenas cuando
se cumple que V (T ) ∩ V (Y ) = {u, v}; es decir, que comparten únicamente los
vértices inicial y final.
T1 = (x1, x5, x3) y T2 = (x1, x4, x3) son dos (x1, x3)-trayectorias internamente
ajenas en la gráfica que muestra en la Figura 1.9, ya que se cumple que:
V (T1) ∩ V (T2) = {x1, x3}.
Figura 1.9: Trayectorias internamente ajenas
Definición. Sea G una gráfica, un camino cerrado:
P = (x1, x2, . . . , xn−1, xn = x1),
con l(P ) ≥ 3, que no repite vértices excepto el vértice final y el vértice inicial;
es decir, x1 = xn lo llamaremos ciclo.
Sabiendo estas definiciones, podemos ahora dar los siguientes resultados.
Teorema 1.5.1. Sean G una gráfica, u y v dos vértices distintos de G. Si G tiene un
uv-camino de longitud l, entonces G tiene una (u, v)-trayectoria de longitud a lo más l.
Demostración. Sean G una gráfica y C = (x0, x1, . . . , xl−1, xl) un camino en G de
longitud l con x0 = u y xl = v. Por demostrar que tenemos una (u, v)-trayectoria P tal
que l(P ) ≤ l. Haremos la demostración sobre el hecho de que la longitud del camino es
finita.
20 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Si en C no se repiten vértices, entonces C es una trayectoria de longitud l. Si tenemos
que xi = xj para i distinto de j, entonces supongamos sin pérdida de generalidad que
i < j; es decir, podemos ver a C como:
C = (x0, x1, . . . , xi−1, xi = xj, xi+1, . . . , xj−1, xj = xi, xj+1, . . . , xl),
entonces si quitamos los vértices (xi+1, xi+2, . . . , xj−2, xj−1), entonces obtenemos el si-
guiente camino C1 = (x0, . . . , xi−1, xi = xj, xj+1, . . . , xl) tal que l(C1) < l. Si en C1
no se repiten vértices, entonces es una (x0, xl)-trayectoria de longitud menor que l.
Supongamos que en C1 tenemos nuevamente un vértice repetido xn = xm con n < m:
C1 = (x0, x1, . . . , xn−1, xn = xm, xn+1, . . . , xm−1, xn = xm, xm+1, . . . , xl),
entonces si quitamos los vértices (xn+1, xn+2, . . . , xm−2, xm−1), entonces obtenemos a C2
un camino tal que
C2 = (x0, x1, . . . , xn−1, xn = xm, xm+1, . . . , xl),
por lo que C2 ⊂ C1 ⊂ C. Si C2 no repite vértices, entonces tenemos una (x0, xl)-
trayectoria tal que l(C1) > l(C2). Si en C2 se repite un vértice, digamos
xk = xp con k < p, entonces
C2 = (x0, x1, . . . , xk−1, xk = xp, xk+1, . . . , xp−1, xk = xp, xp+1, . . . , xl),
y al quitar los vértices (xk+1, xk+2, . . . , xp−2, xp−1) obtenemos un camino:
C3 = (x0, x1, . . . , xk−1, xk = xp, . . . , xl),
tal que l(C2) > l(C3) y además C3 ⊂ C2 ⊂ C1 ⊂ C.
Como el número de vértices de G es finito y K2 es una trayectoria, continuando con
este procedimiento existe un número positivo ρ tal que encontraremos a
Cρ = (u = x0, x1, . . . xl−1, xl = v) un camino que ya no repite vértices, por lo tan-
to, Cρ es una (u, v)-trayectoria tal que l(Cρ) < l y Cρ ⊂ . . . ⊂ C1 ⊂ C.
Por lo tanto, concluimos G tiene una (u, v)-trayectoria de longitud a lo más l, lo
que concluye la demostración.
Proposición 1.1. Si δ(G) = k, entonces existe en G una trayectoria de longitud al
menos k.
Demostración. Sea P = (u0, u1, u2, . . . , um) una trayectoria de longitud máxima en G.
Por demostrar que m ≥ k. Afirmamos que NG(u0) ⊆ V (P ). Si u0 fuera adyacente a al-
gún v ∈ V (G) \ V (P ), entonces se tendría una trayectoria
P ′ = (v, u0, u1, u2, . . . , um) de longitud mayor que la trayectoria P , lo que contradi-
ce la elección de P . Ahora como N(u0) ⊆ V (P ) tenemos que δ(u0) ≤ m, luego como
k = δ(G) ≤ δ(u0) ≤ m, se tiene que P es de longitud al menos k.
1.5. CAMINOS EN GRÁFICAS 21
Lema 1.1. Sean G una gráfica y {u, v} un subconjunto de V (G). Si existen P y Q dos
(u, v)-trayectorias distintas, entonces G tiene un ciclo.
Demostración. Sean P y Q dos (u, v)-trayectorias. Consideremos a
C = (u, P, v) ∪ (v, Q−1, u) un camino cerrado.
Por demostrar que C tiene un ciclo.
Haremos la demostración por inducción sobre la longitud de C.
Base de la inducción. l(C) = 3.
Como la longitud del camino es igual a 3 entonces tenemos los siguientes dos casos
posibles.
Caso 1. El camino cerrado es C = (u, x, v, u), el cual está formado de la siguiente
manera: C = (u, P, v) ∪ (v, Q−1, u). Como x es adyacente a v tenemos que x 6= v.
Caso 2. El camino cerrado es C = (u, v, y, u), el cual está formado de la siguiente
manera: C = (v, P, u) ∪ (u, Q−1, v). Como v es adyacente a y tenemos que v 6= y.
En ambos casos C es un ciclo.
Hipótesis de inducción. Si P ′ y Q′ son dos (u′, v′)-trayectorias distintas en G y
C ′ = (u′, P ′, v′) ∪ (v′, Q′−1, u′) es un camino cerrado tal que l(C ′) < n, entonces C ′
contiene un ciclo.
Paso inductivo. Sean {u, v} un subconjunto de V (G) y C = (u, P, v) ∪ (v, Q−1, u)
un camino cerrado con l(C) = n donde,
P = (u = x0, x1, . . . , xs = v),
Q = (u = y0, y1, . . . , ym = v) y s + m = n.
Por demostrar que C contiene un ciclo.
Caso 1. Si P y Q son tales que V (P ) = V (Q) y A(P ) 6= A(Q), entonces para algún
i y j en {1, 2, ..., s} con i 6= j y k en {1, 2, ..., m} tenemos que xi = yk y xj = yk+1,
entonces podemos obtener el ciclo (xi = yk+1, P, xj = yk) ∪ (yk, yk+1).
Caso 2. Si P 6= Q, entonces existe un xi en la secuencia de vértices (x1, x2, ..., xs) que
no está en la secuencia vértices (y1, y2, ..., ym) o existe un yi en la sucesión de vértices
(y1, y2, ..., ym) que no está en la secuencia de vértices (x1, x2, ..., xs).
Supongamos sin pérdida de generalidad que existe un xi en la secuencia de vértices
(x1, x2, ..., xs) que no está en la secuencia de vértices (y1, y2, ..., ym). Sea
k = mı́n{i : xi ∈ V (P ) y xi /∈ V (Q)}, entonces tenemos lo siguientes casos:
Caso 2.1. k 6= 1.
Para k = mı́n{i : xi ∈ V (P ) y xi /∈ V (Q)}, entonces xk−1 en (V (P ) ∩ V (Q)), así
tenemos las siguientes trayectorias P ′ = (xk−1, xk) ∪ (xk, P, v) y Q′ = (xk−1, Q, v) las
cuales son dos (xk−1, v)-trayectorias distintas y
C ′ = (xk−1, xk) ∪ (xk, P, v) ∪ (v, Q−1, xk−1) = P ′ ∪ (v, Q′−1, xk−1),
es un camino cerrado contenido en C.
22 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Entonces l(C ′) < l(C) = n.
Por hipótesis de inducción C ′ tienen un ciclo γ tal que γ ⊆ C ′ ( C, entonces γ ⊂ C.
Caso 2.2. k = 1.
Sea h = máx{i : xi ∈ V (P ) y xi /∈ V (Q)}, por la elección de h se tiene que xh+1
en (V (P ) ∩ V (Q)).
Así tenemos a las trayectorias siguientes:
P ′′ = (u, P, xh) ∪ (xh, xh+1) y Q′′ = (u, Q, xh+1)
las cuales son dos (u, xh+1)-trayectorias distintas.
C ′′ = (u, P, xh) ∪ (xh, xh+1) ∪ (xh+1, Q−1, u) = P ′′ ∪ (xh+1, Q′′−1, u),
es un camino cerrado contenido en C y por construcción C ′′ es un ciclo.
Por lo tanto, C contiene un ciclo.
1.6. Gráficas conexas
Definición. Una gráfica G es conexa si y solo si para cualquier par de vértices
de G existe una trayectoria que los une.
Decimos que G es una gráfica inconexa si G es no conexa.
Son gráficas conexas las gráficas Kn para toda n en N, los ciclos y las trayec-
torias de cualquier longitud.
Otras condiciones equivalentes a la definición de gráfica conexa pueden es-
tablecerse a través de los siguientes teoremas.
Teorema 1.6.1. Una gráfica G con |V (G)| ≥ 2 es conexa si y solo si para cualquier
partición {V1, V2} de V (G) existe una V1V2-arista.
Demostración. (⇒) Sean G una gráfica conexa, {V1, V2} una partición de V (G), u ∈ V1
y w ∈ V2. Como G es conexa existe una (u, w)-trayectoria en G. Sean
P = (u = x0, x1, . . . , xi, . . . , xn = w) dicha trayectoria y xi el primer vértice de la
sucesión x1, . . . , xn tal que xi en V2, dicho vértice existe ya que xn ∈ V (P ) ∩ V2. Por lo
tanto, xi−1 ∈ V1; es decir, tenemos una V1V2-arista.
(⇐) Demostraremos que G es conexa. Sea {u, w} un subconjunto de V (G), por
demostrar que existe una (u, w)-trayectoria en G. Sea {V1, V2} una partición de V (G)
tal que V1 = {u} y V2 = V (G) − V1. Por hipótesis sabemos que existe una arista uz1
tal que z1 ∈ V2. Si z1 = w, entonces tenemos un uw-camino. Si z1 6= w, entonces
tomamos una nueva partición de V (G): V 1
1 = {u, z1} y V 1
2 = V (G) − V 1
1 . Sabemos
1.7. ALGUNAS OPERACIONES EN GRÁFICAS 23
por hipótesis que existe un arista con extremos en V 1
1 y V 1
2 , sea z2 en V 1
2 , tal que z2
es un vértice extremo de dicha arista. Si z2 = w entonces podemos encontrar un uw-
camino. Si z2 6= w, entonces tomamos la partición {V 2
1 , V 2
2 } tal que V 2
1 = {u, z1, z2}
y V 2
2 = V (G) − V 2
1 . Por hipótesis tenemos una arista con extremos en V 2
1 y en V 2
2 ,
sea z3 en V 2
2 uno de los vértices extremo de dicha arista. Si z3 = w, entonces podemos
encontrar un uw-camino. Si z3 6= w, entonces continuando con este procedimiento, como
G es finita, entonces para una n en N, tenemos una partición {V n
1 , V n
2 } de V (G) tal que
existe una V n
1 zn-arista con zn = w y zn en V n
2 . Por lo tanto, tenemos un uw-camino, y
por el Teorema 1.5.1 tenemos una (u, w)-trayectoria.
Por lo tanto, G es una gráfica conexa.
Definición. Sea G una gráfica. Las componentes conexas de una gráfica G
son las subgráficas de G que son máximas por contención con respecto a la
propiedad de ser conexas. Denotaremos por c(G) al número de componentes
conexas de G.
Observación. Si G es conexa, entonces c(G) = 1. Si c(G) > 1, entonces G es inco-
nexa. Además si G tiene p vértices, entonces c(G) ≤ p.
1.7. Algunas operaciones en gráficas
Definición. Sea G una gráfica, si a ∈ A(G), entonces definimos a la gráfica
G − a como V (G − a) = V (G) y A(G − a) = A(G) − {a}.
Análogamente, tenemos la operación de quitar un vértice de la gráfica y se
define como sigue.
Definición. Sea G una gráfica, si v ∈ V (G), entonces definimos a la gráfica
G − v como V (G − v) = V (G) − {v} y A(G − v) = A(G) − {vx | x ∈ NG(v)}.
Figura 1.10: Ejemplo de G y G − x2
24 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Definición. Sea G una gráfica y S un subconjunto de vértices de G. Decimos
que la gráfica
G − S = (V (G) \ S, A(G) − {uv ∈ A(G) : u ∈ S y v ∈ V (G) \ S}),
esta resulta de restar un subconjunto S de vértices a G.
Figura 1.11: Ejemplo de G y G − S, donde S = {x1, x2}
Definición. Sea G una gráfica y H una subgráfica de G. Definimos a la gráfica
G−H = (V (G)\V (H), A(G)\(A(H)∪{uv ∈ A(G) : u ∈ V (H) y v ∈ V (G)\V (H)})),
esta resulta de restar una subgráfica H de G.
Figura 1.12: Ejemplo de G y G − H
1.7. ALGUNAS OPERACIONES EN GRÁFICAS 25
Por otro lado, tenemos las operaciones para agregar vértices o aristas según sea
necesario, sin embargo, cabe observar que la operación de agregar una arista solo agrega
una arista entre dos vértices no adyacentes de G; es decir, si G es una gráfica y a /∈ A(G),
entonces la gráfica G + a cumple con:
V (G + a) = V (G) y A(G + a) = A(G) ∪ {a},
por lo que esta operación solo aplica para gráficas no completas.
Agregar un vértice v a una gráfica G para efectos de esta tesis: consiste en
hacer adyacente a dicho vértice a cada uno de los vértices de G; es decir,
V (G + v) = V (G) ∪ {v} y A(G + v) = A(G) ∪ {vx : x ∈ V (G)}.
Teorema 1.7.1. Sean G una gráfica conexa y a en A(G). Si a ∈ C tal que C es un
ciclo de G, entonces G − a es conexa.
Demostración. Sean G una gráfica conexa y a en A(G) con a en C tal que C es un ciclo
de G y a = uv.
Consideremos a la gráfica G − a. Por demostrar que para todo subconjunto {x, y}
de V (G − a) existe una (x, y)-trayectoria.
Ahora como V (G−a) = V (G), entonces {x, y} ⊆ V (G) y como G es conexa sabemos
que debe existir al menos una (x, y)-trayectoria
P = (x1, x2, . . . , xn),
por ello tenemos los siguientes casos.
Caso 1. a no está en P .
Entonces P es una (x, y)-trayectoria en G − a.
Caso 2. a está en P
Supongamos sin pérdida de generalidad que para alguna i en {1, 2, . . . , n}
se cumple que u = xi, v = xi+1 y además C empieza en xi y termina con la
arista a = xi+1xi, entonces encontramos el siguiente xy-camino
C = (x, P, u = xi) ∪ (u = xi, C, v = xi+1) ∪ (v = xi+1, P, y)
contenido en G − a, el cual por el Teorema 1.5.1 contiene una xy-trayectoria en G − a.
Por lo tanto, concluimos que G − a es conexa.
26 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
1.8. Vértices de corte, aristas de corte y bloques
Definición. Dada una gráfica G, un vértice v es vértice de corte si cumple
que c(G − v) > c(G), por lo que, para una gráfica conexa, v es un vértice de
corte de G si la gráfica G − v es inconexa.
Observe que en la Figura 1.13 tenemos un ejemplo donde v es un vértice de
corte pues tenemos que c(G − v) = 2 y c(G) = 1.
Figura 1.13: v es un vértice de corte
El siguiente teorema establece las condiciones necesarias y suficientes para
que un vértice v sea de corte.
Teorema 1.8.1. Sea G una gráfica conexa. Un vértice v es de corte si y solo si existen
dos vértices u y w tal que v esta en toda (u, w)-trayectoria de G.
Demostración. (⇒) Sean G una gráfica conexa y v un vértice de corte. Como G − v
no es conexa, entonces tiene al menos dos componentes conexas. Tomemos a u y w en
componentes distintas de G − v, entonces no existen (u, w)-trayectorias en G − v. Sin
embargo, como G es conexa, hay al menos una (u, w)-trayectoria. Por lo tanto, toda
trayectoria entre u y w en G debe contener a v.
(⇐) Sean u y w dos vértices de G. Como por hipótesis sabemos que el vértice v
está en toda (u, w)-trayectoria de G, entonces tenemos que en la gráfica G−v no existe
trayectoria alguna entre los vértices u y w, lo que implica que G − v es inconexa. Por
lo tanto, como G es conexa se sigue que v es vértice de corte en G.
1.8. VÉRTICES DE CORTE, ARISTAS DE CORTE Y BLOQUES 27
Definición. Dada una gráfica G y a ∈ A(G), se dice que a es una arista de
corte o un puente de G si y solo si c(G − a) > c(G).
Teorema 1.8.2. Sea G una gráfica conexa. Una arista a es un puente de G si y solo
si a no pertenece a un ciclo de G.
Demostración. (⇒) Probaremos por contrapositiva. Supongamos que a está en un ciclo
de G. Por demostrar que a no es un puente de G. Como G es conexa y a está en un
ciclo de G, por el Teorema 1.7.1 tenemos que G − a es conexa. Por lo tanto, a no es
puente de la gráfica G.
(⇐) Demostraremos por contradicción. Supongamos ahora, que a = xy es una arista
de G que no está en un ciclo de G y que a no es un puente, esto quiere decir, que G − a
es conexa y por lo tanto existe una (x, y)-trayectoria T en G − a. La unión de a y G − a
produce el siguiente ciclo C = (y, x) ∪ (x, T, y) el cual contiene a a y esto contradice la
hipótesis, concluyendo así el teorema.
Observe la Figura 1.14.
Figura 1.14: a pertenece a un ciclo G
Observación. Al quitar un puente a de una gráfica G quedan exactamente dos com-
ponentes conexas distintas en G − a.
La existencia de un puente implica la existencia de un vértice de corte si
|V (G)| > 2, esto se demuestra a continuación.
28 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Teorema 1.8.3. Sea G una gráfica conexa de orden al menos 3. Si G tiene un puente,
entonces G tiene al menos un vértice de corte.
Demostración. Sean G una gráfica conexa con |V (G)| > 2 y a ∈ A(G) un puente con
extremos u y v. Como a es un puente, G − a es inconexa. Por la observación anterior
G − a tiene dos componentes conexas H1 y H2, supongamos sin pérdida de generalidad
que u ∈ V (H1) y v ∈ V (H2). Como G tiene al menos 3 vértices, entonces existe w en
V (G − a) tal que w es distinto de u y w es distinto de v. Si w /∈ V (H1), entonces en
G−u ⊂ G−a no existen (w, u)-trayectorias. Análogamente, si w /∈ V (H2), entonces en
G − v ⊂ G − a no hay (w, v)-trayectorias, con lo cual concluimos que G − u es inconexa
o G − v es inconexa, esto implica que u o v es un vértice de corte de G (Ver Figura
1.15).
Figura 1.15: G con a un puente en G
Lema 1.2. Si G es una gráfica conexa, v ∈ V (G) tal que v es vértice de corte, entonces
δG(v) ≥ 2.
Demostración. Sea v un vértice de corte y G1, G2, . . . , Gc(G) las componentes conexas
de G−v, con c(G) ≥ 2. En G v es adyacente al menos a un vértice en cada componente
conexa de G, pues G es conexa.
Por lo tanto, se cumple que δG(v) ≥ 2.
1.9. Árboles
Los árboles constituyen una de las clases más importantes de las gráficas.
Intuitivamente, un árbol es una gráfica que en su trazo se asemeja a un árbol
con su ramificación hacia abajo, formalmente su definición es:
1.9. ÁRBOLES 29
Definición. Una gráfica que es conexa y que no tiene ciclos recibe el nombre
de árbol, y la denotamos con T .
En la Figura 1.16 tenemos un ejemplo de un árbol.
Figura 1.16: Árbol
Los vértices de grado uno de un árbol son llamados hojas o vértices termi-
nales. Al conjunto de vértices de grado uno de un árbol T lo denotaremos
como Hojas(T ).
Decimos que B es un bosque, si las componentes conexas de la gráfica B son
árboles; es decir, B es una gráfica que no tiene ciclos; es decir, B es acíclica.
Los siguientes resultados serán nuestras herramientas para realizar las de-
mostraciones de algunos teoremas que serán revisados en los capítulos si-
guientes.
Teorema 1.9.1. Sea G una gráfica conexa, G es un árbol si y solo si toda arista de G
es un puente.
Demostración. (⇒) Sean G un árbol y a en A(G). Como G no tiene ciclos por definición
de árbol, a no está en un ciclo de G y por el Teorema 1.8.2 sabemos que cualquier arista
que no pertenece a un ciclo es un puente, entonces a es un puente de G.
(⇐) Por otro lado, si G es conexa y toda arista a en A(G) es un puente, significa
que toda arista de G no está en un ciclo por el Teorema 1.8.2, por lo que G es acíclica
y conexa. Por lo tanto, es un árbol.
30 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Teorema 1.9.2. Si T es un árbol con al menos dos vértices, entonces T tiene al menos
dos hojas.
Demostración. Sean T un árbol y P = (u1, u2, . . . , um) una trayectoria de longitud
máxima.
Afirmamos que el vértice inicial y el vértice final de P son de grado uno.
Si en P el vértice final no es de grado uno; es decir, δT (um) ≥ 2, entonces existe un
w ∈ V (T ) tal que w 6= um−1 y w es adyacente a um, por ello tenemos los siguientes
casos:
Caso 1. w /∈ V (P ).
En este caso obtenemos la siguiente trayectoria P ′ = (u1, P, um) ∪ (um, w) que es
de longitud mayor que P , pero esto contradice la elección de P , pues P es de longitud
máxima en T .
Caso 2. w ∈ V (P ).
Para algún i en {1, 2, 3, . . . , m − 2} se tiene que w = ui. Con lo que obtenemos el
siguiente ciclo C = (ui, P, um) ∪ (um, ui), lo que contradice el hecho de que T es árbol.
Por lo tanto, la afirmación se sostiene para el vértice final de P , de manera análoga
se demuestra para el vértice inicial de P .
Por lo tanto, en T tenemos al menos dos hojas.
Teorema 1.9.3. Sea T un árbol. Si para un x ∈ V (T ) se tiene que δT (x) = 1, entonces
T − x es árbol.
Demostración. Sea x en V (T ) tal que δT (x) = 1. Por demostrar que T − x es conexa y
no tiene ciclos.
Como T − x ≤ T , entonces T − x no tiene ciclos.
Por demostrar que T es conexa.
Supongamos por contradicción que T − x es inconexa, como T es conexa entonces
x es vértice de corte de T , por el Lema 1.2 sabemos que el δT (x) ≥ 2, lo que contradice
la hipótesis, pues δT (x) = 1. Por lo tanto, T − x es conexa.
El siguiente teorema relaciona el orden y el tamaño de un árbol.
Teorema 1.9.4. Si T es un árbol, entonces q = p − 1, donde q es el tamaño de T y p
es el orden de T .
Demostración. Demostraremos por inducción sobre el número de vértices p.
Base de inducción. Si p = 1, entonces T = K1 por lo que T no tiene aristas; es decir,
q = 1 − 1 = 0.
Si p = 2, entonces T = K2, por lo que q = p − 1 = 2 − 1 = 1.
Hipótesis de inducción. Si T ′ es un árbol con p′ vértices y q′ aristas tal que p′ < p,
entonces q′ = p′ − 1 y p′ ≥ 1.
1.9. ÁRBOLES 31
Paso inductivo. Sea T un árbol con p vértices y q aristas tal que con p > 2. Por el
Teorema 1.9.2 podemos ver que existe un x en V (T ) tal que δT (x) = 1. Consideremos a
T − x, por el teorema anterior T − x es un árbol y por hipótesis de inducción tenemos
que se cumple que |A(T − x)| = |V (T − x)| − 1, entonces
q = |A(T )| = |A(T − x)| + 1 = |V (T − x)| − 1 + 1 = |V (T )| − 1 = p − 1.
Por lo tanto:
q = p − 1.
Lo que concluye la demostración.
Corolario 1.1. Si G es un bosque con p vértices y q aristas, entonces q = p − c(G).
Demostración. Sea G un bosque tal que tiene las siguientes componentes conexas:
G1, G2, . . . , Gc(G).
Para i en {1, 2, . . . , c(G)}, cada Gi es conexa y acíclica, entonces toda Gi es un ár-
bol. Sabemos ahora por el resultado demostrado en el Teorema 1.9.4 que para i en
{1, 2, . . . , c(G)} se cumple que qi = pi − 1, con pi el número de vértices y qi el número
de aristas de cada componente Gi.
Para obtener el número de aristas del bosque tenemos lo siguiente:
q =
c(G)∑
i=1
qi,
c(G)∑
i=1
qi =
c(G)∑
i=1
(pi − 1),
c(G)∑
i=1
(pi − 1) =
c(G)∑
i=1
pi − c(G),
c(G)∑
i=1
pi − c(G) = p − c(G).
Por lo tanto, tenemos que p − c(G) = q.
Teorema 1.9.5. Las siguientes afirmaciones son equivalentes:
1. T es un árbol.
2. Entre cualesquiera dos vértices u y v de T existe una única (u, v)-trayectoria en
T .
3. T es conexa y para cualquier arista a en A(T ) tenemos que T − a es inconexa.
4. T es acíclica y T + uv contiene un único ciclo, para cualesquiera dos vértices no
adyacentes u y v en T .
32 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Demostración. Vamos a demostrar el ciclo de implicaciones (1) ⇒ (2) ⇒ (3) ⇒ (4) ⇒
(1).
Por demostrar que (1) ⇒ (2). Sean u y v en los vértices de T , como T es co-
nexa existe una (u, v)-trayectoria. Por demostrar que es única. Demostraremos esta
implicación por contradicción. Supongamos por contradicción que existen P1 y P2 dos
(u, v)-trayectorias distintas en T . Por el Lema 1.1 sabemos que P1 ∪ P2 contiene un
ciclo. Esto contradice que T sea árbol. Por lo tanto, entre todo par de vértices en T
existe una única trayectoria.
Por demostrar que (2) ⇒ (3). Por demostrar que T es conexa. Como entre cuales-
quiera dos vértices de T existe una única trayectoria, entonces T es conexa. Si xy es
cualquier arista de T , entonces por 2 sabemos que xy es la única (x, y)-trayectoria, por
lo tanto, en T − xy no existen (x, y)-trayectorias; es decir, T − xy es inconexa.
Por demostrar que (3) ⇒ (4). Por demostrar que T es una gráfica acíclica.
Supongamos por contradicción que T no es acíclica. Sea
γ = (x0, x1, x2, . . . , xn = x0) un ciclo en T , por el Teorema 1.8.2 sabemos que T − x1x2
es conexa, lo cual contradice (3). Por lo tanto, T es una gráfica acíclica.
Por demostrar que T + uv contiene un ciclo. Como T es conexa, entonces entre
cualquier par de vértices no adyacentes u y v en T existe P = (u, u1, . . . , um, v) una
(u, v)-trayectoria. Por lo tanto, C = P ∪ (v, u) es un ciclo en T + uv.
Por demostrar que C es único en T + uv. Supongamos por contradicción que C no
es único en T + uv, entonces implica que existe un ciclo C ′ = (u, P ′, v) ∪ (v, u), como
T no tiene ciclos y T + uv si tiene ciclos, entonces uv ∈ A(G). Supongamos sin pérdida
de generalidad que C ′ empieza en u y termina con la arista uv. Así, si P ′ = (u, C ′, v),
entonces como C y C ′ son distintos se sigue que P ′ y P son dos (u, v)-trayectorias
distintas en T , lo que es una contradicción, ya que P es la única (u, v)-trayectoria en
T . Por lo tanto, T tiene un único ciclo.
Por demostrar que (4) ⇒ (1). Sea T una gráfica acíclica, tal que, T +uv contiene un
único ciclo para cualesquiera u y v dos vértices no adyacentes en T . Por demostrar que
T es conexa. Supongamos por contradicción que T no es conexa. Sean x, y dos vértices
en componentes conexas distintas de T , entonces no existe ninguna trayectoria entre
x y y, lo que implica que en T + xy existe una única (x, y)-trayectoria, por lo que no
podemos formar un ciclo, esto contradice la hipótesis que dice que T + uv tienen un
ciclo para cualesquiera dos vértices u y v no adyacentes en T . Por lo tanto, T es conexa
y así T es árbol.
Lema 1.3. Sea G una gráfica conexa con un único ciclo C, tal que G ≇ C. Si P es
una (u, v)-trayectoria contenida en C tal que los vértices de P tienen grado 2 en G,
entonces G − P es un árbol.
Demostración. Sean G una gráfica conexa con un único ciclo C, tal que G ≇ C y
P = (u = u0, u1, u2, ..., un−1, un = v) una (u, v)-trayectoria contenida en el ciclo C tal
que los vértices de P tienen grado 2 en G.
1.9. ÁRBOLES 33
Observemos que como G ≇ C y es conexa, entonces existe al menos un vértice z en
C tal que δG(z) ≥ 3.
Haremos la demostración por inducción sobre el número de vértices de P .
Base de inducción. Si |V (P )| = 1; es decir, u = v con δG(u = v) = 2. Tomemos a w
un vértice del ciclo C tal que es adyacente al vértice u. Consideremos a G′ = G − wu
donde wu en A(G), entonces como wu esta contenida en C, tenemos que G − wu es
conexa y acíclica. Ahora como tenemos que el δG′(u) = 1, por el Teorema 1.9.3 y como
observamos que existe un vértice z tal que δG(z) ≥ 3 tenemos que G′′ = G′ − u es un
árbol y G′′ es isomorfa a G − P .
Si |V (P )| = 2, entonces tenemos que P = (u, v) con δG(u) = δG(v) = 2. Como la
arista uv pertenece al ciclo en G, podemos considerar a G′ = G−uv, entonces obtenemos
que G′ es conexa y acíclica. Ahora como tenemos que
δG′(u) = δG′(v) = 1, entonces por el Teorema 1.9.3 y como observamos que existe
un vértice z tal que δG(z) ≥ 3 tenemos que G′′ = G′ − u es un árbol y G′′′ = G′′ − v es
un árbol y además G′′′ es isomorfa a G − P .
Si |V (P )| = 3, entonces P = (u = u0, u1, u2 = v) con δG(ui) = 2 para i en
{0, 1, 2}. Tomemos a P ′ = (u = u0, u1) una subtrayectoria de la trayectoria P , con
|V (P ′)| = 2, por el caso anterior tenemos que G′ = G − P ′ es un árbol. Consideremos a
G′′ = G′ − u2, entonces por el Teorema 1.9.3 y como observamos que existe un vértice
z tal que δG(z) ≥ 3 sabemos que G′′ es un árbol. Por lo tanto, G − P es un árbol como
se puede ver en la Figura 1.17.
Figura 1.17: G − P
Hipótesis de inducción. Si P ′ = (u = u0, u1, u2, ..., un−1, un−1 = v) es una trayectoria
tal que para todo vértice ui en P con i en {0, 1, 2, ..., n − 1}, se tiene que δG(ui) = 2.
Entonces, G′ = G − P es un árbol.
34 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Paso inductivo. Sea P = (u = u0, u1, u2, ..., un−1, un = v) una trayectoria en G tal
que δG(ui) = 2 para toda i en {0, 1, 2, .., n}. Tomemos los primeros n vértices de P , los
cuales forman una subtrayectoria P ′ de P . Por hipótesis de inducción como |V (P ′)| = n
tenemos que G′ = G−P ′ es un árbol y además sabemos que δG′(un) = 1. Por el Teorema
1.9.3 y la observación sabemos que G′′ = G′ − un es un árbol como se muestra en la
Figura 1.18.
Figura 1.18: G′′ = G′ − un
Ahora, conociendo la definición de árbol y los resultados anteriores, defini-
mos una clase particular de árboles con la que trabajaremos más adelante.
Definición. Decimos que T es un k-árbol si el grado máximo en T es k.
Dada una gráfica G conexa, un problema importante es encontrar una sub-
gráfica G′, de modo que G′ sea un árbol que contenga todos los vértices de
G.
Definición. Decimos que T es un árbol generador de una gráfica conexa G,
si T es una subgráfica generadora de G que es árbol.
Teorema 1.9.6. Toda gráfica conexa tiene un árbol generador.
Demostración. Haremos la demostración por inducción sobre m, donde m es el número
de ciclos en G.
1.9. ÁRBOLES 35
Base. Si m = 0, entonces G no tiene ciclos y es conexa. Por lo tanto, G es un árbol
y cumple que es un árbol generador.
Si m = 1, entonces G tiene un ciclo C. Sea a en A(C) consideremos la gráfica G − a.
Sabemos por el Teorema 1.8.2 que G − a es conexa y sin ciclos, por lo que cumple con
la definición de ser un árbol. Los vértices de G − a son iguales a los de G. Por lo tanto,
G − a es un árbol generador de G.
Hipótesis de inducción. Toda gráfica conexa con m′ ciclos tal que m′ < m tiene un
árbol generador.
Paso inductivo. Sean G una gráfica conexa con m ≥ 2 ciclos y a una arista en un
ciclo de G. Consideremos a G−a, por el Teorema 1.8.2 G−a es conexa y además G−a
tiene un número menor de ciclos que G, por hipótesis de inducción G−a tiene un árbol
generador T , por ello tenemos que V (T ) = V (G − a) = V (G). Por lo tanto, T es un
árbol generador de G.
Observemos que por el Teorema 1.9.5, ahora que tenemos el primer resultado
sobre árboles generadores, podemos notar que en G una gráfica conexa y T
un árbol generador de G, si a ∈ A(G) \ A(T ), entonces T ∪ a tiene un ciclo y
este es único.
Teorema 1.9.7. G es un árbol si y solo si G es acíclica y q = p − 1.
Demostración. (⇒) Como G es un árbol, entonces por definición de árbol G es conexa
y acíclica, por el Teorema 1.9.4 tenemos que q = p − 1.
(⇐) Supongamos que G es una gráfica acíclica y q = p − 1.
Por demostrar que G es conexa. Supongamos que G1, . . . , Gc(G) son las componentes
conexas de G, tal que c(G) ≥ 1. Note que para cada i en {1, 2, ..., c(G)} Gi es un árbol
pues G no tiene ciclos.
Como G es un bosque, entonces por el Corolario 1.1 tenemos que: qi = pi − c(G).
Pero sabemos por hipótesis que q = p−1. Por lo tanto, c(G) = 1, lo que implica que
tenemos una única componente conexa. Así, G es conexa y por la definición de árbol,
G es árbol.
Lema 1.4. Sean T un árbol de orden n ≥ 2 y x un vértice de T , entonces
c(T − x) = (δT (x) − 1) + 1.
Demostración. Sean T un árbol de orden n ≥ 2 y x un vértice de T . Haremos la
demostración por induccción sobre el grado del vértice x.
Base. Si δT (x) = 1, entonces sabemos que T − x es un árbol y c(T − x) = 1. Por
otro lado tenemos:
c(T − {x}) = 0 + 1 = (1 − 1) + 1 = 1(δT (x) − 1) + 1.
36 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Hipótesis de inducción. Si T ′ es un árbol de orden n ≥ 2 y x′ un vértice de T ′, con
δT ′(x′) = r, entonces
c(T − x′) = (δT (x′) − 1) + 1 = r.
Paso inductivo. Sea T un árbol de orden n ≥ 2 y x un vértice de T tal que δT (x) =
r + 1 con r > 1. Por demostrar que c(T − x) = (δT (x) − 1) + 1.
Consideremos a x′ un vértice en T que es adyacente a x, quitamos la arista xx′ a T .
Por el Teorema 1.9.1 sabemos que toda arista de un árbol es un puente y al quitar dicha
arista por la Observación 1.8 tenemos dos componentes conexas T ′ y T ′′, las cuales son
conexas y acíclicas por lo que son árboles. Supongamos sin pérdida de generalidad que
x′ ∈ V (T ′) y x ∈ V (T ′′), entonces δT ′′(x) = r y
δT (x) = δT ′′(x) + 1.
Así tenemos lo siguiente
c(T − x) = c(T ′′ − x) + 1.
Por hipótesis de inducción sabemos que
c(T ′′ − x) = (δT ′′(x) − 1) + 1.
Por lo que
c(T − x) = c(T ′′ − x) + 1
= (δT ′′(x) + 1 − 1) + 1
= (δT (x) − 1) + 1.
Corolario 1.2. Sean T un árbol y x un vértice de T . Si δT (x) = k, entonces T tiene
al menos k hojas.
Demostración. Sean T un árbol y x un vértice de grado k en T . Por el Lema 1.4 sabemos
que
c(T − x) = (δT (x) − 1) + 1
Como δT (x) = k, se tiene que
c(T − x) = (k − 1) + 1 = k.
Cada componente obtenida de T − x es conexa y acíclica por lo que cada una de
ellas es un árbol. Observemos que tenemos dos casos:
Caso 1. Las componentes conexas de T − x son de orden uno. Entonces son hojas
de T .
Caso 2. No todas las componentes de T − x son de orden que uno. Entonces para
componente de orden al menos dos por el Teorema 1.9.2 sabemos que esta tiene al
menos dos vértices de grado uno, por lo que cada una de las componentes de T − x
tiene al menos una hoja de T .
Por lo tanto, T tiene al menos k hojas.
1.9. ÁRBOLES 37
Definición. Sea G una gráfica. Decimos que S un subconjunto de V (G) es
un conjunto independiente, si para todo par de vértices de S estos no son
adyacentes.
Lema 1.5. Sean T un árbol de orden n ≥ 2 y X un conjunto independiente de vértices
en T , entonces
a) el número de hojas de T es igual a
∑
v∈W (δT (v) − 2) + 2, donde
W = {v ∈ V (T ) : δT (v) ≥ 3},
b) el número de componentes conexas de T − X es
∑
x∈X(δT (x) − 1) + 1.
Demostración. a) Sean T un árbol y Hojas(T ) el conjunto de hojas de T . Haremos la
demostración por inducción sobre n el número de vértices T .
Base de inducción. Sea T un árbol de orden 2, entonces el grado de cada vértice de T
es igual a 1. Por lo tanto, W = ∅. Notemos que si W = ∅, entonces
∑
v∈W (δT (v)−2) =
0. Así tenemos que ∑
v∈W
(δT (v) − 2) + 2 = 0 + 2 = 2.
Si T es de orden 3, entonces en T tenemos exactamente un vértice de grado 2 y dos
vértices de grado 1. Por lo tanto, nuevamente se cumple W = ∅ y así tenemos que
∑
v∈W
(δT (v) − 2) + 2 = 0 + 2 = 2.
Sea T un árbol de orden n = 4. Tenemos dos casos.
Caso 1. Si T no tiene vértices de grado 3, entonces tenemos que W = ∅, por lo que
T tiene exactamente dos vértices de grado 2 y dos vértices de grado 1, por lo que se
cumple ∑
v∈W
(δT (v) − 2) + 2 = 0 + 2 = 2 = |Hojas(T )|.
Caso 2. Si T tiene exactamente 3 vértice de grado uno, entonces tenemos lo siguiente∑
v∈W (δT (v) − 2) + 2 = (3 − 2) + 2 = 3 = |Hojas(T )|.
Hipótesis de inducción. Si T ′ es un árbol de orden n − 1 y
W ′ = {v ∈ V (T ′) : δT ′(v) ≥ 3}, entonces
∑
v∈W ′(δT ′(v) − 2) + 2 = |Hojas(T ′)|.
Paso inductivo. Sea T un árbol de orden n con n ≥ 5, por el Teorema 1.9.2 sabemos
que T tiene al menos dos hojas. Sabemos por el Teorema 1.9.3 que si a T le quitamos un
vértice de grado uno la gráfica obtenida sigue siendo un árbol, entonces tomemos a T ′
el árbol obtenido a partir de quitar un vértice h de grado uno a T ; es decir, T ′ = T − h.
Por demostrar que T cumple con el inciso (a). Supongamos que h es adyacente a un
vértice g en T , entonces tenemos tres casos posibles.
Caso 1. Si δT (g) > 3, entonces δT ′(g) ≥ 3 por lo que W = W ′, además por hipótesis
de inducción tenemos que |Hojas(T ′)| =
∑
v∈W ′(δT ′(v) − 2) + 2.
38 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Como en T el vértice h es de grado uno y T ′ = T − h tenemos lo siguiente
|Hojas(T )| = |Hojas(T ′)| + 1 =
∑
v∈W ′
(δT ′(v) − 2) + 2 + 1
=
∑
v∈W ′\{g}
(δT ′(v) − 2) + 2 + 1 + δT ′(g) − 2,
sabemos que δT ′(g) + 1 = δT (g) y como tenemos que δT (g) > 3 se cumple que g ∈ W .
Por lo anterior tenemos que,
∑
v∈W ′\{g}
(δT ′(v) − 2) + 2 + (1 + δT ′(g)) − 2
=
∑
v∈W \{g}
(δT (v) − 2) + 2 + δT (g) − 2 =
∑
v∈W
(δT (v) − 2) + 2.
Caso 2. Si δT (g) = 3, entonces δT ′(g) = 2 y W ′ = W \ {g} y por hipótesis de
inducción tenemos que
|Hojas(T ′)| =
∑
v∈W ′
(δT ′ − 2) + 2.
Como en T el vértice h es de grado uno y T ′ = T − h tenemos lo siguiente
|Hojas(T )| = |Hojas(T ′)| + 1 =
∑
v∈W ′
(δT ′(v) − 2) + 2 + 1,
como δT ′(g) = 2 sumamos el cero siguiente δT ′(g) − 2
∑
v∈W ′
(δT ′(v) − 2) + 2 + (δT ′(g) − 2) + 1
=
∑
v∈W ′
(δT ′(v) − 2) + 2 + (δT ′(g) + 1) − 2,
como δT (g) = 3 = δT ′(g) + 1, entonces g esta en W , por lo que tenemos que
∑
v∈W ′
(δT ′(v) − 2) + 2 + (δT ′(g) + 1) − 2
=
∑
v∈W \{g}
(δT (v) − 2) + 2 + δT (g) − 2 =
∑
v∈W
(δT (v) − 2) + 2.
Caso 3. Si δT (g) = 2, entonces δT ′(g) = 1 y como los vértices con los que se está
trabajando son de grado menor que 3, W y W ′ son iguales, además por hipótesis de
inducción tenemos que |Hojas(T ′)| =
∑
v∈W ′(δT ′(v) − 2) + 2.
1.9. ÁRBOLES 39
Como δT (g) = 2, W ′ = W y como g se convierte en hoja en T ′; tenemos que
δT ′(g) = 1, por lo que se cumple lo siguiente
|Hojas(T )| = |Hojas(T ′)| =
∑
v∈W ′
(δT ′(v) − 2) + 2 =
∑
v∈W
(δT (v) − 2) + 2.
Con lo que finalizamos el inciso (a).
b) Sean T un árbol de orden n ≥ 2 y X un conjunto independiente de vértices en
T . Por demostrar que c(T − X) =
∑
x∈X(δT (x) − 1) + 1.
Haremos la demostración por indución sobre el número de vértices del conjunto X.
Base. Sean T un árbol de orden n ≥ 2 y X = {x} un conjunto independiente de
vértices de T . Por el Lema 1.4 tenemos: c(T − X) = c(T − {x}) = (δT (x) − 1) + 1.
Hipótesis de inducción. Si T ′ es un árbol de orden n ≥ 2 y X ′ un conjunto indepen-
diente de vértices de T ′ tal que |X ′| = r, con r ≥ 1, entonces
c(T ′ − X ′) =
∑
x′∈X′
(δT ′(x′) − 1) + 1.
Paso inductivo. Sean T un árbol de orden n ≥ 2 y X un conjunto independiente de
vértices de T tal que |X| = r + 1, con r > 1. Por demostrar que
c(T − X) =
∑
x∈X
(δT (x) − 1) + 1.
Sea x un vértice en el conjunto X. Consideremos a X ′ = X − {x} el cual es un
conjunto independiente de vértices de T tal que |X ′| = r, por hipótesis de inducción
tenemos que c(T − X ′) =
∑
x′∈X′(δT (x′) − 1) + 1.
Sea Cx una componente conexa de T − X ′, tal que x está en Cx. Por lo que:
a) c((T − X ′) − V (Cx)) = c(T − X ′) − 1 = (
∑
x′∈X′(δT (x′) − 1) + 1) − 1.
NT (X) ⊆ T − X ′, pues X es un conjunto independiente. Así, δT (x) = δCx
(x). Por
el Lema 1.4 tenemos que:
b) c(Cx − x) = (δT (x) − 1) + 1.
Por la hipotesis de inducción, por (a) y (b) y como X = X ′ ∪ {x} es un conjunto
independiente, tenemos que:
c(T − X) = c(T − (X ′ ∪ {x})) = c((T − X ′) − x) = (c(T − X ′) − 1) + c(Cx − x)
= ((
∑
x′∈X′
(δT (x′) − 1) + 1) − 1) + (δT (x) − 1) + 1
=
∑
x′∈X′
(δT (x′) − 1) + (δT (x) − 1) + 1 =
∑
x∈X
(δT (x) − 1) + 1.
40 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
1.10. Gráficas hamiltonianas
El matemático William Rowan Hamilton inventó un juego, que consistía en
recorrer las ciudades más importantes de Europa; sin repetir alguna, volvien-
do a la ciudad de partida. Este juego se propuso en un dodecaedro regular
de madera con veinte clavos (cada uno insertado en una esquina del sólido)
y un trozo de cuerda. A cada clavo se le asignó el nombre de una ciudad y
el objetivo era encontrar una ruta a través de las aristas del dodecaedro que
pasara por todas las ciudades exactamente una vez, y que además terminara
en la ciudad que se había iniciado el recorrido. Para recordar que ciudades
ya habían sido visitadas, se utilizaba la cuerda para conectar los clavos en el
orden correspondiente. La gráfica que representa un dodecaedro en el plano
se puede ver en la Figura 1.19.
Figura 1.19: Gráfica del dodecaedro y su ciclo hamiltoniano
No se tienen indicios de que el juego haya tenido gran éxito popular, pero
en cambio, entre los matemáticos quedó un recuerdo permanente.
Del juego anterior nace la siguiente definición.
Definición. Sea G una gráfica, un ciclo hamiltoniano de G es un ciclo que
pasa por todos los vértices de G.
Una gráfica hamiltoniana es aquella que contiene un ciclo hamiltoniano.
Definición. Sea G una gráfica. P es una trayectoria hamiltoniana en G si
pasa por todos los vértices de G.
1.11. CONEXIDAD PUNTUAL 41
En la Figura 1.19 podemos encontrar un ciclo hamiltoniano del dodecaedro.
A continuación daremos un resultado clásico para las gráficas hamiltonianas.
Teorema 1.10.1. Si G es hamiltoniana, entonces para cualquier subconjunto propio
no vacío S de los vértices de G, c(G − S) ≤ |S|.
Demostración. Sean G una gráfica hamiltoniana y S un subconjunto propio de los
vértices de G no vacío.
Consideremos a G−S y sean G1, G2, . . . , Gc(G−S) las componentes conexas de G−S.
Por demostrar que c(G − S) ≤ |S|.
Como G es hamiltoniana, entonces G tiene un ciclo C tal que V (C) = V (G), por lo
que C pasa por todos los vértices de cada Gi y de S.
Para i en {1, 2, . . . , c(G − S)} consideremos a ui el último vértice de la componente
Gi por el que pasa C, afirmamos que para cada i en {1, 2, . . . , c(G − S)} ui es adya-
cente a un vi en S en C. Si vi no es adyacente a ui, entonces ui es adyacente a un
u′
i ∈ V (Gi) ∩ V (Gi+1), lo que contradice que sean componentes distintas en G. está en
una componente conexa distinta a Gi en G. Por lo que, en S hay al menos c(G − S)
vértices; pues para cada Gi hay un vértice en S.
Por lo tanto, c(G − S) ≤ |S|.
1.11. Conexidad puntual
Definición. Sea G una gráfica, la conexidad puntual de G es el mínimo nú-
mero de vértices que se deben quitar a G para obtener una gráfica inconexa
o una gráfica igual a K1. Se denota por K(G).
Como ejemplo tenemos que:
1. Para la gráfica trivial K1, K(K1) = 0.
2. Para la gráfica completa Kn, K(Kn) = n − 1.
3. Para cualquier ciclo C, K(C) = 2.
4. Para cualquier árbol T de orden p, con p > 1, K(T ) = 1.
5. Para toda gráfica inconexa G, K(G) = 0.
Definición. Sea G una gráfica conexa no completa, un corte puntual de G es
un subconjunto S de V (G), tal que G − S es inconexa.
42 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Observación. Para una gráfica conexa no completa G, con p ≥ 3 tenemos que
K(G) = mı́n{|S| : S es un corte puntual}.
Ahora con esta definición podemos dar lugar a la siguiente:
Definición. Una gráfica G es n-conexa si y solo si K(G) ≥ n.
Todas las gráficas conexas no triviales son 1-conexas.
Observación 1.1. Observemos que para cualquier gráfica G se cumple que
K(G) ≤ δ(G).
Demostración. Sean G una gráfica y v ∈ V (G) tal que δG(v) = δ(G). Consideremos a
S = {v1, v2, ..., vδG(v)} el conjunto de los vecinos de v, entonces v es un vértce aislado
en G − S. Por lo tanto, K(G) ≤ δ(G).
Definición. Sean G una gráfica, u y v en V (G) tal que u no es adyacente a v
y S ⊆ V (G). Decimos que S es un uv-conjunto separador de G, si se cumple
que u y v están en componentes conexas distintas de G − S. Decimos que S
es un uv-conjunto separador mínimo de G si
|S| = mín{|U | : U es un uv-conjuto separador y uv /∈ A(G)}.
Ahora enunciaremos el teorema de Menger y varios resultados que son con-
secuencia de este, algunos no serán demostrados en esta tesis.
Teorema. (Menger[5]) Sean G una gráfica, u y v dos vértices no adyacentes de G. Si
S es un uv-conjunto separador mínimo de G, entonces la cardinalidad de S es igual al
máximo número de (u, v)-trayectorias internamente ajenas en G.
Teorema 1.11.1. [5] Sea G una gráfica de orden n ≥ 2, G es n-conexa si y solo si para
todo par de vértices u y v existen al menos n (u, v)-trayectorias internamente ajenas
en G.
Demostración. (⇒) Sea G una gráfica n-conexa y supongamos por contradicción que
existen dos vértices u y v tal que el máximo número de trayectorias internamente ajenas
entre ellos en G es l, donde l < n. Si uv no está en el conjunto de aristas de G, por el
Teorema de Menger tenemos que el número de vértices que separan a u y v es l, por la
definición de conexidad puntual tenemos que K(G) ≤ l. Por lo que, K(G) < n, lo cual
contradice la hipótesis. Si uv está en las aristas de G, entonces el máximo número de
(u, v)-trayectorias internamente ajenas en G − uv es l − 1. Por el teorema de Menger
tenemos que el número de vértices que separan a u y v en G−uv es l−1, por la definición
1.11. CONEXIDAD PUNTUAL 43
de conexidad puntual tenemos que K(G − uv) ≤ l − 1. Por lo que, K(G − uv) < n − 1.
Por lo tanto, existe un subconjunto U de V (G − uv) con cardinalidad menor que n − 1
tal que (G − uv) − U es una gráfica inconexa o la gráfica trivial. Por ello al menos una
de las siguientes gráficas G − (U ∪ {u}) y G − (U ∪ {v}) es inconexa lo que implica que
K(G) < n lo que también es una contradicción, pues G es n-conexa.
(⇐) Demostraremos por contradicción. Supongamos que G es una gráfica no trivial
tal que no es n-conexa, pero que para todo par de vértices distintos existen al menos n
trayectorias internamente ajenas entre ellos. Claramente, G no es completa.
Como G no es n-conexa, entonces K(G) < n. Sea W un conjunto con K(G) vértices
de G; es decir, |W | < n, tal que G − W es inconexa. Tomemos a u y v en componentes
distintas de G − W . Los vértices u y v son no adyacentes por estar en componentes
distintas de G − W ; por hipótesis hay n trayectorias internamente ajenas entre ellos.
Por el teorema de Menger tenemos que, u y v no pueden ser separados por menos de n
vértices, lo que es una contradicción puesto que estamos separando a u y a v con W , el
cual es cardinalidad menor que n.
Lema 1.6. [5] Sean G una gráfica n-conexa, S = {u1, u2, ..., un} un subconjunto de
vértices de G de cardinalidad n y v /∈ V (G). Si
G′ = (V (G) ∪ {v}, A(G) ∪ {uiv : ui ∈ S}),
entonces G′ es n-conexa.
Demostración. Haremos la demostración por inducción sobre n.
Base de inducción. Sea n = 1. Como G es 1-conexa, entonces G es conexa. Si
S = {u1}, entonces por construcción G′ es conexa. Por lo tanto, G′ es 1-conexa.
Hipótesis de inducción. Si H es una gráfica (n − 1)-conexa, S ⊆ V (G) tal que
|S| = n − 1 y v /∈ V (G), entonces H ′ = (V (H) ∪ {v}, A(H) ∪ {uiv : ui ∈ S}) es
(n − 1)-conexa.
Paso de inducción. Sean G una gráfica n-conexa con n > 1,
S = {u1, u2, ..., un} un subconjunto de vértices de G, v /∈ V (G) y
G′ = (V (G) ∪ {v}, A(G) ∪ {uiv : ui ∈ S}). Sea {x, y} un subconjunto de V (G′).
Por demostrar que entre todo par de vértices x y y de G′ existen al menos n (x, y)-
trayectorias internamente ajenas.
Si {x, y} un subconjunto de V (G), entonces G es n-conexa pues tenemos que existen
al menos n (x, y)-trayectorias internamente ajenas.
Si v en {x, y}, entonces supongamos sin pérdida de generalidad que v = y. Consi-
deremos los siguientes casos:
Caso 1. x /∈ S; es decir, x ∈ V (G) − S.
Entonces xv /∈ A(G′). Por lo que, S es un xv-conjunto separador mínimo de car-
dinalidad n en G′, entonces por el Teorema de Menger sabemos que en G′ existen al
menos n (x, v)-trayectorias internamente ajenas.
44 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Caso 2. x ∈ S.
Entonces xv ∈ A(G′). Consideremos el conjunto S ′ = S − {x} y a
G′′ = G − xv. Como G es n-conexa, entonces en particular G es (n − 1)-conexa. Como
G′′ ∼= H ′, donde H ′ = (V (G) ∪ {v}, A(G) ∪ {uiv : ui ∈ S ′}), por hipótesis de induc-
ción tenemos que G′′ es (n − 1)-conexa, por el Teorema 1.11.1 tenemos al menos n − 1
(x, v)-trayectorias internamente ajenas en G′′. Como xv ∈ A(G′), entonces tenemos en
G′ al menos n (x, v)-trayectorias internamente ajenas.
Por el Teorema 1.11.1 tenemos que G′ es n-conexa.
Teorema 1.11.2. [5] Si G es una gráfica n-conexa y {v, v1, v2, . . . , vn} un subconjunto
con n + 1 vértices distintos en G, entonces para 1 ≤ i ≤ n existen (v, vi)-trayectorias
tales que {(v, vi)-trayectorias : i ∈ {1, ..., n}} es un conjunto de trayectorias interna-
mente ajenas.
Demostración. Dada una gráfica G n-conexa y {v, v1, v2, . . . , vn} es un conjunto de n+1
vértices distintos en G, podemos construir una nueva gráfica H a partir de G al agregar
un nuevo vértice u a G junto con todas las aristas uvi con i en {1, 2, . . . , n}; es decir,
H = (V (G)∪{u}, A(G)∪{uvi : i ∈ {1, 2, ..., n}}). Por el lema anterior H es n-conexa.
Por el Teorema 1.11.1 sabemos que existen al menos n trayectorias internamente ajenas
entre v y u en H, sabemos que u es adyacente a cada vi con i en {1, 2, . . . , n}, entonces
para cada (v, u)-trayectoria en H tenemos una (v, vi)-trayectoria con i en {1, 2, . . . , n}
en G.
Teorema 1.11.3. [5] Sea G una gráfica n-conexa con n ≥ 2, entonces cualesquiera n
vértices de G pertenecen a un ciclo común.
Lema 1.7. Si G es n-conexa, entonces G + x es (n + 1)-conexa, con x /∈ V (G).
Demostración. Por demostrar que G + x es (n + 1)-conexa. Sean u y v dos vértices
de G + x. Por demostrar que existen al menos n + 1 (u, v)-trayectorias internamente
ajenas. Consideremos los siguientes casos:
Caso 1. u y v están en V (G).
Entonces como G es n-conexa, por el Teorema 1.11.1 sabemos que en G existen al
menos n (u, v)-trayectorias internamente ajenas. Además por construcción de G + x el
vértice x es adyacente a todo vértice de G; así que entre u y v existe la trayectoria
(u, x) ∪ (x, v) la cual pasa por x en G + x, por ello tenemos entre todo par de vértices
de G al menos n + 1 trayectorias internamente ajenas en G + x.
Caso 2. u = x o v = x.
Supongamos sin pérdida de generalidad que u = x, tomemos a v1, v2, ..., vn n vértices
de distintos G, tal que para toda i en {1, 2, ..., n} vi 6= v. Por el Teorema 1.11.2 como G
es n-conexa hay al menos n (v, vi)-trayectorias internamente ajenas, denotadas por Tviv
para i en {1, 2, . . . , n}. Como x es adyacente a todo vértice de G tenemos las siguientes
1.12. INDEPENDENCIA. 45
n trayectorias en G + x, para i en {1, 2, . . . , n} (x, vi) ∪ Tviv y con la arista xv tenemos
al menos n + 1 trayectorias internamente ajenas en G + x.
Por lo tanto, G + x es (n + 1)-conexa.
1.12. Independencia.
Ya que en los resultados centrales de esta tesis se pide que las gráficas sean
n-conexas y además tengan cierta condición de independencia, es necesario
presentar las siguientes definiciones.
Recordemos la definición de conjunto independiente. Sea G una gráfica. De-
cimos que S un subconjunto de V (G) es un conjunto independiente, si para
todo par de vértices de S estos no son adyacentes.
Teniendo la definición de un conjunto independiente de vértices en G ahora
podemos definir el número de independencia como sigue:
Definición. Sea G una gráfica. El número de independencia de G, denotado
por α(G), es α(G) = máx{|S| : S es un conjunto independienteenG}. A continua-
ción en la Figura 1.20, se muestra un conjunto indepeniente S = {x1, x4, x9}
de G. Observemos que {x1x9, x1x4, x4x9} * A(G).
Figura 1.20: S = {x1, x4, x9} es un conjunto independiente
46 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
1.13. Teorema Chvátal-Erdös
Veamos un teorema que simplificará la demostración del resultado propuesto
por Chvátal y Erdös.
Teorema 1.13.1. Sea G una gráfica con al menos 3 vértices. Si para algún n ≥ 2,
G es n-conexa y no contiene subconjuntos independientes de cardinalidad mayor a n,
entonces G tiene un ciclo hamiltoniano.
Demostración. Sea G una gráfica con al menos 3 vértices, tal que para un n ≥ 2 entero,
G es n-conexa. Como n ≥ 2 por el Teorema 1.11.3 G tiene al menos un ciclo. Sea C un
ciclo de longitud máxima en G. Por el Teorema 1.11.3 la longitud de C es mayor o igual
que n.
Supongamos que G no contiene ciclos hamiltonianos, entonces hay un vértice x,
tal que x no está en el ciclo C. Ya que G es n-conexa existen n trayectorias interna-
mente ajenas que inician en x y terminan en n vértices de C (Teorema 1.11.2). Sean
x1, x2, . . . , xn los vértices finales de estas trayectorias, denotamos por Txxi
a la (x, xi)-
trayectoria. Para cada i en {1, 2, . . . , n} sea yi el vértice sucesor del vértice xi en C, en
un orden fijo de los vértices de C.
Con esto tenemos dos casos posibles:
Caso 1. Existe para un vértice yi, con i en {1, 2, . . . n} tal que es adyacente a x.
Supongamos sin pérdida de generalidad que C empieza y termina en xi. Entonces
el ciclo C ′ = (yi, C − xiyi, xi) ∪ (xi, T −1
xix
, x) ∪ (x, yi) es de longitud mayor a la longitud
de C ya que contiene a los vértices de C y a x, lo que es una contradicción (ver Figura
1.21).
Figura 1.21: C ′
1.13. TEOREMA CHVÁTAL-ERDÖS 47
Caso 2. Para toda i en {1, 2, . . . , n} se cumple que yi no es adyacente a x.
Consideremos el conjunto formado por los vértices yi y el vértice x un subconjunto
de cardinalidad n + 1 de V (G), por las hipótesis del teorema no puede ser un conjunto
independiente, por lo cual existen dos vértices yi y yj que son adyacentes en G con
{i, j} ⊆ {1, 2, . . . n}, i 6= j. Tomamos a xi y xj los respectivos vértices antecesores de
yi y yj en C. Supongamos sin pérdida de generalidad que C empieza y termina en xj.
Tomemos el ciclo
C ′′ = (xi, T −1
xxi
, x) ∪ (x, Txxj
, xj) ∪ (xj, C−1 − xjyj, yi) ∪ (yi, yj) ∪ (yj, C − xiyi, xi)
(ver Figura 1.22).
Figura 1.22: C ′′
El cual es de longitud mayor a la longitud de C, esto nuevamente es una contradic-
ción.
Por lo tanto, G tiene un ciclo hamiltoniano.
Con el teorema recién demostrado podemos ahora revisar el teorema pro-
puesto por Chvátal y Erdös.
Teorema 1.13.2. [9] (Chvátal, P. Erdös 1972) Sean n ≥ 1 un entero y G una gráfica
n-conexa. Si α(G) ≤ n + 1, entonces G tiene una trayectoria hamiltoniana.
Demostración. Caso 1. G es una gráfica n-conexa y α(G) < n + 1.
Como G satisface las hipótesis del Teorema 1.13.1 ya que no tiene conjuntos inde-
pendientes de más de n vértices, entonces G tiene un ciclo hamiltoniano y por ello G
tiene una trayectoria hamiltoniana.
Caso 2. G es una gráfica n-conexa y α(G) = n + 1.
48 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Consideremos la gráfica G + x obtenida a partir de G al agregar un nuevo vértice
x adyacente a todos los vértices de G. Por el Lema 1.7 G + x es (n + 1)-conexa y no
tiene un conjunto independiente de más de n + 1 vértices. Por lo que G + x cumple las
hipótesis del Teorema 1.13.1 para n+1; pues no puede tener conjuntos independientes de
cardinalidad n+2. Por lo tanto, por el Teorema 1.13.1 G+x tiene un ciclo hamiltoniano;
por lo cual G tiene una trayectoria hamiltoniana.
Recordemos que el objetivo de esta tesis es el estudio de los k-árboles en
gráficas, para k = 2 tenemos que un 2-árbol es una trayectoria. Entonces el
Teorema 1.13.2 nos da condiciones para obtener un 2-árbol generador de G.
1.14. Dominación en gráficas
Definición. Sea G una gráfica, S ⊆ V (G) es un conjunto dominante de G si
para todo v en V (G) − S, v es adyacente a algún vértice u, con u ∈ S.
Figura 1.23: Conjunto dominante S
Un conjunto S de G es un conjunto dominante de tamaño mínimo, si S es
un conjunto dominante de G y para cualquier otro conjunto dominante S ′
se verifica que |S| ≤ |S ′|.
Definición. Sean G una gráfica, m ≥ 0 un entero y X un subconjunto de vérti-
ces de G. Entonces el conjunto m-dominante de X, denotado por Domim(X),
se define como el siguiente conjunto de vértices:
Domim(X) = {v ∈ V (G) : dG(v, X) ≤ m}.
1.15. DIGRÁFICAS 49
Si los vértices de un subconjunto o una subgráfica Y de G están incluidos
en Domim(X), entonces decimos que X m-domina Y . Por lo tanto, una H
subgráfica de G 0-domina a G si y solo si H es gráfica generadora de G.
Ejemplo. Sea X = {x13, x14, x15, x16} un conjunto 2 dominante de G, entonces
Domi2(X) = {x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12}.
Figura 1.24: Domi2(X)
1.15. Digráficas
Definición. Una digráfica D es un par ordenado (V (D), F (D)), donde V (D)
es un conjunto finito no vacío de objetos, al que llamaremos conjunto de
vértices de D, y F (D) es una colección de pares ordenados de vértices de D,
al que llamaremos conjunto de flechas de D.
Por como se define F (D) se permiten flechas del tipo (v, v) a las cuales lla-
maremos lazos. Ahora, observemos que entre dos vértices distintos u y v de
V (D) podemos tener dos o más flechas entre ellos de la forma (u, v), en este
caso diremos que son multiflechas y que la digráfica D es una multidigráfica.
Definición. Decimos que una digráfica D es simple si no admite lazos ni mul-
tiflechas. En esta tesis al hablar de digráficas estaremos haciendo referencia
a digráficas simples salvo que se indique lo contrario.
50 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Dada una digráfica D, la cardinalidad de V (D) es el orden de D y la car-
dinalidad de F (D) es el tamaño de D. El orden de cualquier digráfica es al
menos uno.
Definición. Sea D una digráfica, diremos que u es adyacente a v si (u, v) en
F (D) o (v, u) en F (D). Si (u, v) en F (D), diremos que u es vértice inicial y v
es vértice final de la flecha (u, v), respectivamente. Con esto para una flecha
(u, v) en F (D) decimos que el vértice u es adyacente hacia el vértice v, y que
el vértice v es adyacente desde el vértice u.
La representación geométrica en el plano de una digráfica consiste en poner
a los vértices como puntos y a las flechas como un arco que tiene una punta
de flecha hacia el vértice final de la flecha, como se muestra en la Figura
1.25.
Figura 1.25: Representación geométrica de una digráfica
Definición. Sean D una digráfica y x en V (D). Decimos que N+(x) es la
vecindad exterior de x si N+(x) = {v ∈ V (D) : (x, v) ∈ F (D)}. Decimos que
N−(x) es la vecindad interior de x si N−(x) = {v ∈ V (D) : (v, x) ∈ F (D)}.
Definición. El ingrado de un vértice v de la digráfica D es el número de
flechas que tienen como vértice final a v y lo denotaremos por δ−
D(v). El
exgrado de un vértice v de la digráfica D es el número de flechas que tienen
como vértice incial al vértice v y se denota por δ+
D(v).
Teniendo la definición de ingrado y exgrado de un vértice podemos dar la
definición de grado.
1.15. DIGRÁFICAS 51
Definición. El grado de un vértice v en una digráfica D es la suma del exgrado
y el ingrado del vértice, el cual es denotado por δD(v); es decir,
δD(v) = δ+
D(v) + δ−
D(v).
Definición. Un camino dirigido en una digráfica D es una sucesión de vértices
C = (u0, u1, u2, ..., un) tal que para toda i en {0, 1, ..., n − 1} (ui, ui+1) en F (D) y
se define a su longitud como n.
Definición. Un camino no dirigido en una digrafica es una suceción de vérti-
ces C = (x0, x1, x2, ..., xn) tal que para i en {0, 1, ..., n−1} se cumple que (xi, xi+1)
en F (D) o (xi+1, xi) en F (D).
Definición. Una trayectoria dirigida es un camino dirigido que no repite
vértices.
Definición. Un camino dirigido cerrado es un camino dirigido que inicia y
termina en el mismo vértice.
Definición. Un ciclo dirigido C = (x0, x1, x2, ..., xn = x0) es un camino dirigido
cerrado que no repite vértices, salvo el primero y el último y su longitud es
mayor o igual que 2. Un ciclo no dirigido es un camino no dirigido cerrado
que no repite vértices, salvo por el primero y el último y su longitud es
mayor o igual que 2.
Definición. Decimos que una digráfica D es conexa si entre todo par de
vértices de D existe un camino no dirigido.
Ahora definamos lo que conoceremos como un árbol dirigido en esta tesis.
Definición. A una digráfica que es conexa y no tiene ciclos dirigidos ni ciclos
no dirigidos la llamaremos árbol dirigido, y la denotaremos por
−→
T .
Diremos que r es un vértice raíz de
−→
T , si el ingrado de r cumple que δ−
−→
T
(x) = 0
y además δ+
−→
T
(x) ≥ 1. Decimos que x un vértice de
−→
T es una hoja de
−→
T si
cumple que δ−→
T
(x) = δ−
−→
T
(x) = 1.
52 CAPÍTULO 1. CONCEPTOS ELEMENTALES Y PRIMEROS RESULTADOS
Definición. Sea
−→
T un árbol dirigido, diremos que
−→
T es un árbol exterior
dirigido si este tiene raíz r y para todo vértice x distinto de la raíz se
cumple que δ−
−→
T
(x) = 1 y δ+
−→
T
(x) ≥ 0.
Por ejemplo en la Figura 1.26, podemos observar un árbol
−→
T dirigido, donde
r es la raíz, se cumple que ∆−(
−→
T ) = 1 y ∆+(
−→
T ) = 2. Las flechas se dirigen a
los vértices de grado uno saliendo del vértice raíz r ya que se cumple que
δ−
−→
T
(r) = 0, δ+
−→
T
(r) ≥ 1; para i = 1, 2, ..., 9 tenemos que δ−
−→
T
(xi) = 1 y δ+
−→
T
(xi) ≥ 0.
Figura 1.26:
−→
T árbol exterior dirigido con raíz r
Capítulo 2
Árboles generadores con grados
acotados
Examinamos en el capítulo anterior el resultado propuesto por Chvátal y
Erdös; el cual nos permite encontrar en una gráfica n-conexa con α(G) ≤ n+1
un 2-árbol generador. A partir de este teorema M. Las Vergnas se pregunta
si toda gráfica n-conexa G con α(G) ≤ n + l − 1 contiene un árbol generador
con a lo más l vértices finales.
En 1979 S. Win da una prueba a la pregunta anterior; su resultado establece
que toda gráfica n-conexa con número de independencia α(G) ≤ n+c contiene
un árbol generador con a lo más c + 1 vértices terminales.
Por otro lado, en 1988 Víctor Neumann Lara y Eduardo Rivera Campo
presentan dos resultados que buscan dar una generalización a la propuesta
de Chvátal y Erdös. Los cuales son los siguientes:
1. Sea G una gráfica n-conexa con número de independencia α(G). Si
α(G) ≤ 1 + ns para algún entero positivo s, entonces G tiene un árbol gene-
rador con grado máximo a lo más s + 1.
2. Sean G una gráfica n-conexa con número de independencia α(G), s y c
dos enteros tales que 3 ≤ s y 0 ≤ c ≤ n. Si α(G) ≤ 1 + n(s − 1) + c, entonces
G tiene un árbol generador T con grado máximo a lo más s + 1 y que no
contiene más de c vértices de grado s + 1.
El primer resultado en términos de k-árbol para k = s + 1 es; Sea G una
gráfica n-conexa con número de independencia α(G). Si α(G) ≤ 1 + n(k − 1)
53
54 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
para algún entero positivo k, entonces G tiene un k-árbol generador. Por
lo que en el segundo resultado tendremos un k-árbol generador y que no
contiene más de c vértices de grado k, al que denotamos como (k, c)-subárbol
generador.
Comenzaremos este capítulo con un lema de apoyo que nos servirá para
demostrar los resultados de V. Neumann Lara y E. Rivera Campo.
Será necesario tener presentes los conceptos de árbol exterior dirigido con
raíz y las operaciones de agregar y quitar vértices a una gráfica, así como
también tener en cuenta los teoremas vistos para árboles y para gráficas
n-conexas en el capítulo 1.
2.1. Lema de apoyo
Definición. Sean D una digráfica y v ∈ V (D), decimos que un vértice v− de
V (D) es un vértice antecesor de v si tenemos la flecha (v−, v) en D.
Para realizar la demostración del resultado principal de este capítulo, es
necesario primero revisar el siguiente lema.
Lema 2.1. [13] Sean
−→
T un árbol exterior dirigido, R y B dos subconjuntos ajenos
de V (T ) tal que (R ∪ B) ∩ (Hojas(T )) = ∅ y N+(R ∪ B) ∩ R = ∅. Para cada
b ∈ B, sean xb un vértice fijo en N+(B) y X(B) = {xb : b ∈ B}. Existe una función
φ : N+(R) ∪ (N+(B) \ X(B)) −→ Hojas(T ) ∪ N−(R) que satisface las siguientes
condiciones.
1. Si u ∈ N+(R) ∪ (N+(B) \ X(B)), entonces existe Tuφ(u) tal que esta es una
(u, φ(u))-trayectoria dirigida en
−→
T .
2. Si Tuφ(u) y Tvφ(v) son trayectorias dirigidas ajenas por vértices, entonces u 6= v.
3. Si u 6= v, entonces al menos uno de los vértices v− y u− es un vértice de Tφ(u)φ(v).
4. El rango de φ (N+(R) ∪ (N+(B) \ X(B))) es un conjunto independiente en
−→
T .
Demostración. Sean Y = {(b, a) ∈ F (
−→
T ) : b ∈ B y a 6= xb}. Definimos a
−→
H como
la gráfica tal que V (
−→
H ) = V (
−→
T ) − R y F (
−→
H ) = F (
−→
T − R) − Y ) una nueva gráfica
obtenida a partir de
−→
T , por definición de Y y
−→
T las componentes conexas de
−→
H son
árboles exteriores dirigidos. Más aún, cada vértice u ∈ N+(R) ∪ (N+(B) − X(B)) es
raíz de la componente conexa de
−→
Hu de
−→
H ; la cual contiene a u, además los vértices
terminales en
−→
Hu son vértices que están en Hojas(T ) o están en N−(R), por lo que
podemos definir a
φ : N+(R) ∪ (N+(B) \ X(B)) −→ Hojas(T ) ∪ N−(R)
2.1. LEMA DE APOYO 55
tal que para u un vértice en N+(R)∪(N+(B)\X(B)) φ(u) es un vértice en Hojas(T )∪
N−(R).
Primero veamos que φ es función. Por demostrar que si u = v, entonces
φ(u) = φ(v). Supongamos por contradicción que φ(u) 6= φ(v), entonces tenemos que
−→
Hu 6=
−→
Hv, lo que implica que u 6= v, lo que es una contradicción. Por lo tanto, φ es
función. Veamos que φ es inyectiva. Por demostrar que si φ(u) = φ(v), entonces u = v.
Supongamos por contradicción que u 6= v, entonces tenemos
−→
Hu 6=
−→
Hv, lo que implica
que φ(u) 6= φ(v), lo que es una contradicción. Por lo tanto, φ es inyectiva.
Demostremos la condición 1. Sabemos que entre todo par de vértices de
−→
T existe
una única trayectoria, entonces Tuφ(u) es una trayectoria dirigida en
−→
Hu, como
−→
Hu ⊂
−→
T ,
entonces Tuφ(u) es una trayectoria dirigida de
−→
T .
La condición 2 se satisface pues si tomamos a u 6= v tenemos dos componentes
−→
Hu
y
−→
Hv tal que
−→
Hu ∩
−→
Hv = ∅, por lo tanto, las trayectorias Tuφ(u) y Tvφ(v) cumplen que
V (Tuφ(u)) ∩ V (Tvφ(v)) = ∅; es decir, son ajenas por vértices.
Ahora demostraremos la condición 3. Sean r la raíz de
−→
T , u y v dos
vértices distintos en N+(R) ∪ (N+(B) − X(B)) y Trφ(u) y Trφ(v) dos trayectorias
dirigidas que inician en la raíz de
−→
T . Sea w ∈ V (Trφ(u)) ∩ V (Trφ(v)) tal que
Tφ(u)φ(v) = Twφ(u) ∪ Twφ(v). Por la condición 2 sabemos que Tuφ(u) y Tvφ(v) son ajenas por
vértices, lo que nos da los siguientes casos:
Caso 1. Si w = φ(u), entonces v− ∈ V (Tφ(u)φ(v)).
Caso 2. Si w = φ(v), entonces u− ∈ (Tφ(u)φ(v)).
Caso 3. Si φ(v) 6= w o φ(u) 6= w, entonces como {w} ⊆ V (Trφ(u))∩V (Trφ(v)) tenemos
que v− en V (Twφ(v)) y u− en (Twφ(u)).
Por lo tanto, la condición 3 se satisface.
Por último demostraremos que se satisface la condición 4. Supongamos por contra-
dicción que Hojas(T )∪N−(R) no es un conjunto independiente, entonces tenemos una
flecha de φ(u) a φ(v) en F (
−→
T ). Como Tuφ(u) y Tvφ(v) son ajenas por vértices tenemos
que v = φ(v), por lo tanto, tenemos que v− = φ(v). Por construcción sabemos que
v− está en R ∪ B y φ(v) está en Hojas(T ) ∪ N−(R) pero por hipótesis tenemos que
(R ∪ B) ∩ (Hojas(T )) = ∅, por lo que tenemos una contradicción.
Por lo tanto, Hojas(T ) ∪ N−(R) es un conjunto independiente.
56 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
Ejemplo de
−→
T y
−→
H
2.2. Árboles generadores con grado acotado
Teorema 2.2.1. [13] Sean G una gráfica n-conexa con número de independencia α(G),
s y c dos enteros tales que 3 ≤ s y 0 ≤ c ≤ n. Si α(G) ≤ 1 + n(s − 1) + c, entonces G
tiene un árbol generador con grado máximo a lo más s + 1 y que contiene a lo más c
vértices de grado s + 1.
Demostración. Llamamos a T un (s + 1, c)−subárbol de G, si es un árbol de G que
cumple que ∆(T ) ≤ s + 1 y el número de vértices de grado s + 1 es menor o igual a c.
Sea T un (s + 1, c)-subárbol de G con el máximo número de vértices posibles de G.
Si T es un (s+1, c)-subárbol árbol generador de G, entonces la demostración finaliza.
Supongamos por contradicción que T no es un árbol generador de G, entonces po-
demos escoger un vértice w de G que no está en T . Para i 6= j con {i, j} ⊆ {1, 2, . . . , l},
sea P = {Π1, Π2, . . . , Πl} la colección máxima de trayectorias de w a T en G, tal que
Πi ∩ Πj = {w} y |Πi ∩ V (T )| = 1. Para cada i, sea ri el único vértice de Πi en T .
Supongamos sin pérdida de generalidad, que δT (r1) ≤ δT (r2) ≤ . . . ≤ δT (rl). Por la
elección de T , T cumple lo siguiente:
1. El grado máximo de T es s + 1.
2. T tiene a lo más c vértices de grado s + 1.
3. T tiene el mayor número de vértices posibles bajo las condiciones 1 y 2.
Por (1) tenemos que para todo vértice u ∈ V (T ) se cumple que δT (u) ≤ s+1, por lo
que tenemos que δT (rl) ≤ s+1. Por otro lado, afirmamos que s ≤ δT (r1). Si δT (r1) < s,
entonces T junto con la trayectoria Π1 sería un T ′ subárbol de G con más vértices que
T que satisface las condiciones (1) y (2), pues tenemos que δT ′(r1) = δT (r1) + 1 < s + 1
2.2. ÁRBOLES GENERADORES CON GRADO ACOTADO 57
y δT ′(u) = δT (u) ≤ s + 1 para todo vértice u de T ′ distinto de r1 lo que constituye una
contradicción a la elección de T .
Por el Teorema 1.11.1 sabemos que l es al menos n pues G es n-conexa.
Llamamos R a el conjunto de todos los vértices ri; es decir, R = {r1, r2, . . . , rl}. Sea
t el número de vértices en R con grado s en T . Sea B = {b1, b2, . . . , bm} el conjunto de
vértices en V (T ) − R que tienen grado s + 1 en T . Como c es el número de vértices de
grado s + 1 en T tenemos que c ≥ m + l − t de lo que podemos obtener m ≤ c − l + t.
Esto nos lleva a dos casos.
Caso 1. Si t > 0, entonces δT (r1) = s y entonces T ∪ Π1 es un subárbol que tiene
grado a lo más s + 1. Como T es un (s + 1, c)-subárbol y es máximo en cantidad de
vértices de G con grado s + 1, por lo que T contiene exactamente c vértices de grado
s + 1 de lo contrario podemos obtener a T ′ = T ∪ Π1 con más vértices de grado s + 1,
lo que contradice que T sea máximo; por lo tanto, tenemos que m = c − l + t.
Caso 2. Si t = 0, entonces δT (r1) = s + 1 para i = 1, 2, . . . .l, por lo que c ≥ l, pero
sabemos que l ≥ n ≥ c, por lo tanto, m = l = n, por lo que B es vacío; es decir, m = 0.
Consideremos a
−→
T el árbol exterior dirigido con raíz r y B 6= ∅. Observe que como
B ∈ V (T ) − R, entonces R y B son dos conjuntos ajenos, además
(R ∪ B) ∩ Hojas(T ) = ∅ pues todo vértice de Hojas(T ) es de grado uno. Demostrare-
mos ahora que N+(R ∪ B) ∩ R = ∅. Para esto, supongamos que N+(R ∪ B) ∩ R 6= ∅,
lo que implica considerar los siguientes dos casos.
Caso 1. Si ri en N+(R) ∩ R, entonces tenemos a (rj, ri) una flecha de
−→
T , por lo que
tenemos a H = T ∪ Πi ∪ Πj con un único ciclo
Υ = (ri, Πi, w) ∪ (w, Πj, rj) ∪ (rj, ri),
ahora bien por el Lema 2.1 T ′ = (T − (ri, rj)) ∪ Πi ∪ Πj es un árbol de G. Como
δT (ri) = δT ′(ri) y δT (rj) = δT ′(rj) implica que T ′ es un (s + 1, c)-subárbol de G con
más vértices que T lo que es una contradicción.
Caso 2. Si ri en N+(B) ∩ R, entonces tenemos a (bj, ri) una flecha de
−→
T , por lo que
tenemos a H = T ∪ Π1 ∪ Πi con un único ciclo
Υ = (ri, Πi, w) ∪ (w, Π1, r1) ∪ (r1, Tr1bj
, bj) ∪ (bj, r1)
donde Tr1bj
es la trayectoria que une a r1 y a bj en T , ahora bien por el Lema 2.1
T ′ = (T − (bj, ri)) ∪ Π1 ∪ Πi es un árbol de G. Como tenemos que δT (bj) = δT (bj) − 1,
δT (r1) = δT ′(r1) + 1 y δT (ri) = δT ′(ri) implica que T ′ es un (s + 1, c)-subárbol de G con
más vértices que T , lo que es una contradicción.
Por lo tanto, tenemos que N+(R ∪ B) ∩ R = ∅.
Como N+(R ∪ B) ∩ R = ∅ con R y B dos conjuntos ajenos y además tenemos que
(R ∪ B) ∩ Hojas(T ) = ∅, tomemos a X(B) = {xb ∈ N+(B) : b ∈ B} y
φ : N+(R) ∪ (N+(B) − X(B)) −→ N−(R) ∪ Hojas(T )
58 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
donde W = N+(R) ∪ (N+(B) − X(B)). Por el Lema 2.1 φ es una función uno a uno,
entonces |W | = |N+(R) ∪ (N+(B) − X(B))|.
Observemos que como
−→
T es un árbol exterior dirigido con raíz y por el Lema 2.1,
no contamos a las flechas en
−→
T que van de R a B, por lo que el grado de R se reduce
en uno. Además para los vecinos de B estamos quitando también a X(B), por lo que
el grado de B se reduce en 2. También notemos que como para todo vértice v en
−→
T
tenemos que δ−
−→
T
(v) ≤ 1, entonces |N+(R) ∩ (N+(B) − X(B))| = 0.
Por lo tanto, tenemos que:
|W | = |N+(R)| + |(N+(B) − X(B))|
= (t(s) + (l − t)(s + 1) + (c − l + t)(s + 1)
≥ (1 + t(s − 1) + (l − t)s) + (c − l + t)(s − 1)
= 1 + ts − t + ls − ts + (c − l + t)(s − 1)
= 1 + ls − t + l − l + (c − l + t)(s − 1)
= 1 + l(s − 1) + (l − t) + (c − l + t)(s − 1)
≥ 1 + l(s − 1) + c.
Como tenemos que l ≥ n, entonces:
1 + l(s − 1) + c ≥ 1 + n(s − 1) + c.
Por lo tanto, |W | ≥ 1 + n(s − 1) + c
Como α(G) ≤ 1 + n(s − 1) + c, entonces W ∪ {w} no puede ser un conjunto inde-
pendiente, por lo que tenemos una arista dg en A(G) con ambos vértices en W ∪ {w}.
Además, como P = {Π1, Π2, . . . , Πl} es el conjunto máximo de trayectorias de w a
T , si a es un vértice que está en T y es adyacente a w en G, entonces a está en R
pues en caso contrario aw sería una trayectoria de w a T que no está en P . Si w = d
o w = g, entonces afirmamos que d y g están en W , es decir que, d 6= w y g 6= w.
Supongamos sin pérdida de generalidad que d = w, entonces tenemos una wW -arista
en G. Como W está en los vértices de T y P = {Π1, Π2, . . . , Πl} es el conjunto máximo
de trayectorias ajenas de w a T , afirmamos que el vértice g está en W que a su vez está
en R, pues en caso contrario wg sería una trayectoria ajena distinta a las Πi para i en
{1, 2, . . . , l} que no está en P. Por lo tanto g ∈ R ∩ W, pero por el Lema 2.1 tenemos
2.2. ÁRBOLES GENERADORES CON GRADO ACOTADO 59
que R ∩ W ⊂ R ∩ (Hojas(T ) ∪ N−(R)) = ∅, lo que implica que R ∩ W = ∅ lo que es
una contradicción. Por lo tanto d y g están en W. Por el lema anterior sabemos que W
es independiente, por lo tanto, dg ∈ A(G) − A(T ).
Tomemos dos vértices u y v en N+(R) ∪ (N+(B) − X(B)) tal que φ(u) = d y
φ(v) = g. Por la condición 3 del Lema 2.1 tenemos un vértice
p(d, g) en {u−, v−} ∩ V (Tdg).
Probaremos que a partir de T podemos construir un nuevo árbol T ′ que contiene a
los vértices de T y el vértice w. Para obtener este nuevo árbol T ′ borraremos algunas
aristas de T y uniremos las componentes obtenidas de borrar las aristas de T por medio
de la arista dg y algunas de las trayectorias que están en P = {Π1, Π2, . . . , Πl}.
Queremos que el nuevo árbol T ′ sea de la forma (s + 1, c)-subárbol para llegar a
una contradicción, pues T es un (s + 1, c)-subárbol con el mayor número de vértices
posibles de G. Buscaremos que al momento de quitar y agregar aristas, T ′ cumpla con
tener c vértices de grado s + 1 y que el grado máximo de T ′ sea s + 1. Esto nos lleva a
considerar los siguientes casos.
Caso 1. Si se agrega una arista a un vértice u ∈ V (T ) tal que 1 ≤ δT (u) < s, no hay
problema pues no se altera el grado máximo ni el número de vértices de grado s + 1.
Caso 2. Si se agrega una arista a un vértice u ∈ V (T ) tal que δT (u) = s+1, entonces
deberemos borrar una arista que incida en u para así conservar el grado máximo igual
a s + 1.
Caso 3. Si se agrega una arista a un vértice u que es de grado s en T haremos a
u = r1 y que δ(p(d, g)) = s+1, entonces se obtendrá un nuevo vértice de grado s+1, por
lo que ahora tendremos c + 1 vértices de grado s + 1, por lo tanto deberemos quitar un
arista que esté en T y que incida en un vértice de grado s+1, sin pérdida de generalidad
quitaremos una arista que incida en el vértice p(d, g) para así obtener nuevamente c
vértices de grado s + 1.
En cualquiera de los tres casos debemos tener cuidado de obtener nuevamente un
árbol.
Por lo tanto, podremos concluir que T ′ cumplirá con las condiciones de ser (s+1, c)-
subárbol de G al igual que T .
Ahora bien analizaremos los casos posibles que se tienen para obtener el árbol T ′ a
partir de T .
Consideremos las siguientes observaciones.
Observación 1. La gráfica T + dg tiene un único ciclo C y además (T + dg) − ac con
ac ∈ A(C) − dg es un árbol.
Demostración. Ya que T es un árbol y {d, g} ⊆ V (T ) tal que dg /∈ A(T ), enton-
ces por el Teorema 1.9.5 sabemos que T + dg tiene un único ciclo C. Si tomamos una
arista ac ∈ A(C) − dg, entonces (T + dg) − ac es conexa y acíclica puesto que le esta-
mos quitando un arista al único ciclo de T +dg, por lo tanto, (T +dg)−ac es un árbol. ♦
60 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
Observación 2. Para cualquier i en {1, 2, . . . , l}, la gráfica T ∪ Πi es un árbol.
Demostración. Como T es un árbol y Πi es una trayectoria de T a w tal que
T ∩ Πi = ri, por lo tanto, podemos concluir que T ∪ Πi es acíclica y además por
el Teorema 1.9.5 concluimos que para toda i en {1, 2, . . . , l} T ∪ Πi es un árbol. ♦
Sea h un vértice en V (Tdg) adyacente a p(d, g) y para cada η ∈ N−(R) sea i(η) tal
que ηri(η) es una flecha en
−→
T .
Caso 1. Cuando {d, g} ⊆ Hojas(T ).
1.1) Si p(d, g) en R, entonces tomemos a p(d, g) = ri para alguna i en {1, 2, ..., l}.
Definimos a T ′ = ((T + dg) − rih) ∪ Πi. Por la observación 1 y 2 sabemos que es un
árbol.
Veamos que T ′ cumpla con ser un (s + 1, c)-subárbol. Sabemos que
δT ′(ri) = δT (ri) + 1 − 1 = s + 1,
δT ′(d) = δT (d) + 1 = 2,
δT ′(g) = δT (g) + 1 = 2 y
δT (h) < δT ′(h) < s + 1.
Por lo tanto, no se afecta la cantidad de vértices de grado s + 1. Por lo que T ′ es un
(s + 1, c)-subárbol como se muestra en la Figura 2.1.
Figura 2.1: T ′.
2.2. ÁRBOLES GENERADORES CON GRADO ACOTADO 61
1.2) Si p(d, g) en B, entonces tomemos a p(d, g) = bi para alguna i en {1, 2, ..., m}.
Definimos a
T ′ = ((T + dg) − bih) ∪ Π1.
Por las observaciones 1 y 2 cumple con ser un árbol.
Veamos que T ′ es un (s + 1, c)-sub árbol. Sabemos que para bi y r1 se cumple que:
δT (bi) = s + 1 y δT (r1) = s,
entonces tenemos por construcción de T ′ que:
δT ′(r1) = δT (r1) + 1,
δT ′(bi) = δT (bi) − 1 = s,
δT ′(d) = δT (d) + 1,
δT ′(g) = δT (g) + 1 y
δT ′(h) < δT (h) < s + 1.
Por lo tanto, tenemos c vértices de grado s + 1 en T ′. Por lo que T ′ es un
(s + 1, c)-subárbol como se muestra en la Figura 2.2.
Figura 2.2: T ′.
62 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
Caso 2. d ∈ Hojas(T ) y g ∈ N−(R).
2.1) Si ri(g) en V (Tdg) y δT (ri(g)) = s + 1, entonces definimos a
T ′ = ((T + dg) − gri(g)) ∪ Πi(g).
Por las observaciones 1 y 2, T ′ cumple con ser un árbol.
Veamos que T ′ es un (s + 1, c)-subárbol. Por construcción de T ′ tenemos que:
δT ′(ri(g)) = δT (ri(g)) + 1 − 1, δT ′(d) = δT (d) + 1 = 2 y δT (g) < δT ′(g) < s + 1.
Por lo tanto, T ′ es un (s + 1, c)-subárbol pues no se altera el grado máximo s + 1 ni el
número de vértices de grado s + 1 (Figura 2.3).
Figura 2.3: T ′.
2.2) Si ri(g) /∈ V (Tdg), entonces tenemos que p(d, g) en R o p(d, g) en B.
2.2.a) Si p(d, g) en R, entonces p(d, g) = rj para alguna j en {1, 2, ..., l}. Definimos
a T ′ = (((T +dg)−rjh)−gri(g))∪Πj ∪Πi(g). Por las observaciones 1 y 2 T ′ es un árbol.
Como p(d, g) = rj sabemos que δT (rj) = s + 1. Por construcción de T ′ tenemos que
δT ′(rj) = δT (rj) + 1 − 1, δT ′(d) = δT (d) + 1 = 2, δT (g) < δT ′(g) < s + 1 y
δT ′(h) < δT (h) < s + 1.
Por lo que nuevamente tenemos c vértices de grado s+1. Por lo tanto, T ′ es un (s+1, c)-
subárbol como se muestra en la Figura 2.4.
Figura 2.4: T ′.
2.2. ÁRBOLES GENERADORES CON GRADO ACOTADO 63
2.2.b) Si p(d, g) en B, entonces tenemos que p(d, g) = bj para alguna j en {1, 2, ..., m}.
Definimos a
T ′ = (((T + dg) − bjh) − gri(g)) ∪ Π1 ∪ Πi(g).
Por las observaciones 1 y 2 T ′ es un árbol.
Veamos que T ′ es un (s + 1, c)-subárbol. Sabemos que para p(d, g) = bj y r1 se
cumple que δT (bj) = s + 1 y δT (r1) = s. Por construcción de T ′ tenemos que:
δT ′(bi) = δT (bj) − 1 = s,
δT ′(r1) = δT (r1) + 1 = s + 1,
δT ′(d) = δT (d) + 1,
δT (g) < δT ′(g) < s + 1 y
δT ′(h) < δT (h) < s + 1.
Por lo que el número de vértices de grado s + 1 es igual a c y el grado máximo de T ′ es
s + 1. Por lo tanto, T ′ es un (s + 1, c)-subárbol como se muestra en la Figura 2.5.
Figura 2.5: T ′.
64 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
Caso 3. d ∈ N−(R) y g ∈ Hojas(T ), en este caso T ′ se construye de forma análoga
al caso 2 al intercambiar a d por g y a g por d.
Caso 4. d ∈ N−(R) y g ∈ N−(R).
4.1) Si ri(d) y ri(g) están en V (Tdg), entonces definimos a
T ′ = (((T + dg) − dri(d)) − gri(g)) ∪ Πi(d) ∪ Πi(g)
el cual por las observaciones 1 y 2 y por la definición de las trayectorias del conjunto
P es un árbol.
Veamos que T ′ es un (s + 1, c)-subárbol. Observemos que por la construcción de T ′
δT ′(d) = δT (d) + 1 − 1 < s + 1 y que δT ′(g) = δT (g) + 1 − 1 < s + 1. Además tenemos
que:
δT ′(ri(d)) = δT (ri(d)) + 1 − 1,
δT ′(ri(g)) = δT (ri(g)) + 1 − 1,
δT (g) < δT ′(g) < s + 1 y
δT (d) < δT ′(d) < s + 1.
Por lo que tenemos c vértices de grado s + 1 en T ′. Por lo tanto, T ′ es un
(s + 1, c)-subárbol como se muestra en la Figura 2.6.
Figura 2.6: T ′.
2.2. ÁRBOLES GENERADORES CON GRADO ACOTADO 65
4.2) ri(d) /∈ V (Tdg) y ri(d) /∈ V (Tdg).
4.2.a) Si p(d, g) en R, entonces p(d, g) = rq para alguna q en {1, 2, ..., l}. Definimos
a
T ′ = ((((T + dg) − rqh) − gri(g)) − dri(d)) ∪ Πq ∪ Πi(d) ∪ Πi(g).
Por las observaciones 1, 2 y la definición de las trayectorias en P sabemos que T ′ es un
árbol.
Veamos que T ′ es un (s + 1, c)-subárbol. Como p(d, g) en R, entonces
δT (rq) = s + 1.
Por construcción de T ′ tenemos que δT ′(rq) = δT (rq) + 1 − 1. También quitamos las
aristas dri(d) y gri(g), por lo que:
δT ′(dri(d)) = δT (dri(d)) + 1 − 1,
δT ′(gri(g)) = δT (gri(g)) + 1 − 1,
δT ′(h) < δT (h) < s + 1,
δT (d) < δT ′(d) < s + 1 y
δT (g) < δT ′(g) < s + 1.
De esta manera no se altera el número de vértices de grado s+1. Por lo que concluimos
que T ′ es un (s + 1, c)-subárbol como se muestra en la Figura 2.7.
Figura 2.7: T ′.
66 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
4.2.b) Si p(d, g) en B, entonces tenemos que p(d, g) = bq para alguna q en {1, 2, ..., m}.
Definimos a
T ′ = ((((T + dg) − bqh) − gri(g)) − dri(d)) ∪ Π1 ∪ Πi(d) ∪ Πi(g).
Por las observaciones 1, 2 y la definición de las trayectorias del conjunto P sabemos
que T ′ es un árbol.
Veamos que T ′ es un (s + 1, c)-subárbol. Como p(d, g) = bq en B, bq cumple que
δT (bq) = s + 1 y r1 es de grado s en T . Por construcción de T ′ tenemos que δT ′(bq) =
δT (bq) y δT ′(r1) = δT (r1) + 1, también al quitar las aristas dri(d) y gri(g) tenemos que:
δT ′(dri(d)) = δT (dri(d)) + 1 − 1,
δT ′(gri(g)) = δT (gri(g)) + 1 − 1,
δT ′(h) < δT (h) < s + 1,
δT (d) < δT ′(d) < s + 1 y
δT (g) < δT ′(g) < s + 1.
Por lo tanto, T ′ es un (s + 1, c)-subárbol como se muestra en la Figura 2.8.
Figura 2.8: T ′.
2.2. ÁRBOLES GENERADORES CON GRADO ACOTADO 67
Estos casos cubren todas las combinaciones posibles y en cada uno de los casos
obtenemos un T ′ que es un (s + 1, c)-subárbol de G con más vértices que T , esto
contradice la elección de T.
Por lo tanto, T es un (s + 1, c)-subárbol generador.
Las condición del teorema anterior son justas en el sentido que para cada n, s
y c con 0 < n, 3 ≤ s y 0 ≤ c ≤ n, la gráfica completa bipartita F = Kn,2+n(s−1)+c
es n-conexa, con número de independencia
α(G) = 2 + n(s − 1) + c
y no tiene un (s + 1, c)-subárbol generador. Como F es una gráfica bipartita
completa el subconjunto independiente máximo es el de cardinalidad 2 +
n(s − 1) + c. Lo que nos da dos casos a analizar.
a) Si c < n, entonces todo árbol generador de F tiene grado máximo s + 1 y
además contiene c + 1 vértices de grado s + 1.
b) Si c = n, entonces todo árbol generador de F tiene al menos un vértice
de grado mayor que s + 1.
Teorema 2.2.2. Sea G una gráfica n-conexa con número de independencia α(G). Si
α(G) ≤ 1 + ns para algún entero positivo s, entonces G tiene un árbol generador con
grado máximo a lo más s + 1.
Demostración. Por el teorema anterior y el resultado de Chvátal y Erdös solo es nece-
sario hacer la demostración para cuando s = 2.
Sea T un árbol de G con grado máximo menor que 4; que contenga la mayor cantidad
de vértices posibles de G. Siguiendo el mecanismo de la demostración del teorema
anterior, supongamos que T no es un árbol generador de G, por lo que existe un vértice
w en G − T . Sea P = {Π1, Π2, . . . , Πl} la colección máxima de trayectorias de w a
T , tal que para toda {i, j} en {1, 2, . . . , l}, con i 6= j se tiene que Πi ∩ Πj = {w};
para cualquier trayectoria en P se cumple que |V (T ) ∩ V (Πi)| = 1. Para cada i sean
ri el único vértice de Πi en T y R = {r1, r2, . . . , rl} el conjunto de vértices ri. Por el
teorema de Menger sabemos que l ≥ n y por la elección de T para toda i = {1, 2, . . . , l}
δT (ri) = 3.
Sea t el número de vértices en R con grado s en T . Sea B = {b1, b2, . . . , bm} el
conjunto de vértices en V (T )−R que tienen grado s+1 en T . Si aplicamos el Lema 2.1
para B = ∅ y tomamos a
−→
T un árbol exterior dirigido con raíz r1. Podemos como en el
teorema anterior encontrar una arista a ∈ A(G)−A(T ) con sus extremos en el conjunto
W = φ[N+(R)]. Por ello tenemos nuevamente 4 casos, tal que son análogos a los casos
1, 2, 3 y 4 de la demostración del Teorema 2.2.1 donde en cada uno se encuentra un
68 CAPÍTULO 2. ÁRBOLES GENERADORES CON GRADOS ACOTADOS
T ′ con más vértices que T , tal que δT ′(u) ≤ 3 para toda u ∈ V (T ′) y V (T ) ∪ {w} y
V (T ) ∪ {w} ⊂ V (T ′).
Lo que conduce a una contradicción. Por lo tanto, T es un (s + 1)-árbol generador
de G.
Las condiciones del Teorema 2.2.2 son justas en el sentido que para cada n y
s con 0 < n y 3 ≤ s, la gráfica completa bipartita F = Kn,2+ns es n-conexa, con
número de independencia α(G) = 2+ns y no tiene un s+1-subárbol generador.
Como F es una gráfica bipartita completa el subconjunto independiente
máximo es el de cardinalidad 2 + ns. Por lo que todo árbol generador de F
tiene al menos un vértice de grado mayor que s + 1.
Capítulo 3
k-árboles m-dominantes en gráficas
Después de 26 años de que Víctor Neumann Lara y Edurardo Rivera Campo
presentaran el resultado visto en el capítulo 2 que permite encontrar un
k-árbol generador. En 2014, Mikio Kano, Kenta Ozeki, Masao Tsugaki y
Guiying Yan proponen una generalización para dicho resultado; en cual se
obtiene un k-árbol m-dominante. Un k-árbol m-dominante T de G, es una
subgráfica de G que es un k-árbol y que además cumple que para todo
v ∈ V (G) se tiene que dG(v, T ) ≤ m. Este resultado es el siguiente:
Teorema 3.2.1. Sean k ≥ 2, m ≥ 0, n ≥ 1 tres números enteros positivos y
G una gráfica n-conexa. Si α2(m+1)(G) ≤ (k − 1)n + 1, entonces G tiene un
k-árbol que m-domina a G.
Este resultado también generaliza el teorema de Broersma:
Teorema 3.0.1. [5] Sean m ≥ 0 y n ≥ 1 dos números enteros positivos y G una gráfica
n-conexa. Si α2(m+1)(G) ≤ n + 1, entonces G tiene una trayectoria que m-domina a G.
La demostración de este teorema la podemos encontrar en el artículo “Exis-
tence of ∆k-cycles and ∆k-paths” [5]. Observemos que si se obtiene una
trayectoria que m-domina a G, podemos decir que encontramos un 2-árbol
que m-domina a G.
En este capítulo se da la demostración del Teorema 3.2.1. Posteriormente
proponemos un algoritmo para encontrar un k-árbol m-dominante, en una
gráfica que cumpla las condiciones del Teorema 3.2.1; deducido a partir de
dicha demostración. Por último se da una posible solución al problema de
distribución de agua en una red pequeña, usando k-árboles m-dominantes.
69
70 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Para comenzar este capítulo enunciaremos algunas definiciones necesarias
junto con algunos lemas que apoyarán la demostración del teorema central
de este capítulo. También debemos tener presentes los resultados vistos para
árboles y gráficas n-conexas, así como las definiciones vistas para digráficas
y conjuntos dominantes en el capítulo 1.
3.1. Definiciones y primeros resultados
Comenzaremos recordando algunas definiciones y notaciones necesarias para
el desarrollo de este capítulo.
Sea T un árbol, denotaremos por PT (u, v) a la única trayectoria en T que
conecta a los vértices u y v en T .
Definición. Sean G una gráfica, m ≥ 0 un entero y X un subconjunto de vérti-
ces de G. Entonces el conjunto m-dominante de X, denotado por Domim(X),
se define como el siguiente conjunto de vértices:
Domim(X) = {v ∈ V (G) : dG(v, X) ≤ m}.
Si los vértices de un subconjunto o una subgráfica Y de G están incluidos
en Domim(X), entonces decimos que X m-domina a Y . Por lo tanto, una H
subgráfica de G 0-domina a G si y solo si H es una gráfica generadora de G.
Sean
−→
T un árbol exterior dirigido y v un vértice en
−→
T ; decimos que u es
vértice sucesor de v si (v, u) en F (
−→
T ), el número de sucesores de v es igual a
δ−→
T
(v) − 1. Denotamos al conjunto de vértices sucesores de v como Hijos(v).
Sea G una gráfica. Para un entero l ≥ 2, el invariante αl(G) de una gráfica
G se define como sigue:
αl(G) = máx{|S| : S ⊆ V (G), dG(x, y) ≥ l para todo {x, y} ⊆ S, x 6= y}.
Observemos que el número de independencia α(G) es igual a α2(G).
Veamos un ejemplo para l = 3.
3.1. DEFINICIONES Y PRIMEROS RESULTADOS 71
Figura 3.1: Gráfica G con α3(G).
Veamos los casos posibles para calcular α3(G). Sea S ⊆ V (G) tal que cumple
que dG(x, y) ≥ 3 para todo {x, y} ⊆ S con x 6= y y |S| = α3(G).
Caso 1. Si el vértice v1 está en S, entonces dG(v1, vi) ≤ 2 para i en {2, 3, 4}, por
lo que los vértices v2, v3 y v4 no pueden estar en S. Además, si v5 está en S,
entonces v6 no está en S. Es análogo si v6 está en S por ser adyacente a v5.
Caso 2. Si v2 está en S, entonces dG(v1, vi) ≤ 2 para i en {1, 3, 4}, por lo que los
vértices v1, v3 y v4 no pueden estar en S. Además, si v5 está en S, entonces
v6 no está en S. Es análogo si v6 está en S por ser adyacente a v5.
Caso 3. Si v3 está en S, entonces dG(v1, vi) ≤ 2 para i en {1, 2, 4}, por lo que
los vértices v1, v2 y v4 no pueden estar en S. Además, v6 está en S ya que es
el único vértice que cumple que dG(v3, v6) ≥ 3.
Caso 4. Si v4 está en S, entonces v4 es el único vértices que puede estar en
S, pues la dG(v4, vi) ≤ 2 para i en {1, 2, 3, 5, 6}.
Caso 5. Si v5 está en S, entonces dG(v5, vi) ≤ 2 para i en {3, 4, 6}, por lo que los
vértices v3, v4 y v6 no pueden estar en S. Además, si v1 está en S, entonces
v2 no está en S. Es análogo si v2 está en S por ser adyacente a v1.
72 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Caso 6. Si v6 está en S, entonces dG(v6, vi) ≤ 2 para i en {4, 5}, por lo que
los vértices v4 y v5 no pueden estar en S. Además, si v1 está en S, entonces
v2 y v3 no están en S. Es análogo si v2 o v3 está en S por estar en el ciclo
C3 = (v1, v2, v3).
En los seis casos obtuvimos que |S| = 2, por lo tanto, α3(G) = 2.
Ahora, veamos una serie de lemas que serán necesarios para la demostración
del teorema central de este capítulo.
Lema 3.1. Sean m ≥ 1 un entero, G una gráfica conexa, H un subconjunto de vértices
de G, y1 y y2 dos vértices distintos de Domim(H) − H. Supongamos que existen dos
conjuntos de vértices ajenos S(y1) y S(y2) de 〈H〉G tal que:
1. Para i en {1, 2} se cumple que dG(yi, S(yi)) = m y
dG(yi, 〈H〉G − S(yi)) ≥ m + 1,
2. No existe una (S(y1), S(y2))-trayectoria en G tal que sus vértices internos están
contenidos en G − H, en particular no hay aristas entre S(y1) y S(y2),
entonces dG(y1, y2) ≥ 2(m + 1).
Demostración. Haremos la demostración por contradicción.
Supongamos que dG(y1, y2) ≤ 2m + 1. Sean P la (y1, y2)-trayectoria más corta en G
que une a y1 con y2 y P ′
i la (yi, S(yi))-trayectoria más corta en G que une al conjunto
S(yi) con el vértice yi para i en {1, 2}. Afirmamos que los vértices interiores de P ′
i están
contenidos en G−H, ya que si esto no pasa tendríamos un vértice v ∈ V (〈H〉G)−S(yi) y
por (1), tenemos que dG(yi, 〈H〉G −S(yi)) ≥ m+1, lo que contradice que dG(yi, S(yi)) =
m.
Afirmamos que la (y1, y2)-trayectoria pasa por 〈H〉G. Supongamos por contradicción
que la (y1, y2)-trayectoria no pasa por 〈H〉G, entonces el camino
(S(y1), P ′
1, y1) ∪ (y1, P, y2) ∪ (y2, P ′
2, S(y2))
contiene a una (S(y1), S(y2))-trayectoria, la cual sus vértices internos están contenidos
en G − H, lo que contradice (2), por lo tanto, P pasa por 〈H〉G.
Sean z1 y z2 dos vértices en la trayectoria P tal que z1 es el primer vértice y z2 el
último vértice que están en 〈H〉G y que pertenecen a P , entonces por (1), sabemos que
para i en {1, 2} se tiene que dG(zi, yi) ≥ m, por lo que debemos considerar los siguientes
casos.
Caso a) z1 6= z2. Tenemos que dG(y1, y2) = dG(y1, z1) + dG(z1, z2) + dG(z2, y2), sabe-
mos que dG(yi, zi) ≥ m y dG(z1, z2) ≥ 1, por lo que tenemos que
dG(y1, z1) + dG(z1, z2) + dG(z2, y2) ≥ 2m + dG(z1, z2) ≥ 2m + 1, por lo que dG(y1, y2) ≥
2m + 1 pero tenemos que dG(y1, y2) ≤ 2m + 1, por lo tanto,
dG(y1, y2) = 2m + 1. Esto implica que dG(z1, z2) = 1, dG(y1, z1) = m y
3.1. DEFINICIONES Y PRIMEROS RESULTADOS 73
dG(y2, z2) = m, por lo que por (1) z1 en S(y1) y z2 en S(y2) con z1 y z2 adyacen-
tes en G, lo que contradice la hipótesis (2).
Caso b) Supongamos que z1 = z2. Tenemos dos subcasos.
Caso b.1) Si z1 en S(y1) entonces tenemos el siguiente camino
(z1, P ′
1, y2) ∪ (y2, P ′
2, S(y2)) que contiene una (S(y1), S(y2))-trayectoria cuyos vértices
interiores están en G − H, lo que contradice (2).
Caso b.2) Si z2 /∈ S(y1), entonces z1 ∈ V (〈H〉G) − S(y1) y por (1) tenemos que
dG(y1, z1) ≥ m + 1. Debido a esto sabemos que z2 /∈ S(y2), entonces
z1 ∈ V (〈H〉G) − S(y2) y por (1) dG(y1, z1) ≥ m + 1 Si z2 estuviera en S(y2) sería
análogo al caso (b.1), por lo tanto, z1 = z2 /∈ S(y1) ∪ S(y2), por (1) sabemos que
dG(y1, z1) ≥ m + 1 y dG(y2, z2) ≥ m + 1. Por lo tanto, tenemos que
dG(y1, y2) = dG(y1, z1) + dG(z2, y2) ≥ 2(m + 1),
lo que nuevamente es una contradicción.
Lema 3.2. Sean m ≥ 1 un entero positivo, G una gráfica conexa, H una subgráfica
de G, y ∈ Domim(H) − V (H) y w ∈ V (G) − Domim(H) dos vértices. Si existe un
conjunto de vértices S(y) ⊆ V (H) tal que
1. dG(y, S(y)) = m y dG(y, 〈H〉G − S(y)) ≥ m + 1; y
2. no existe una (w, S(y))-trayectoria cuyos vértices internos estén contenidos en
G − H,
entonces dG(w, y) ≥ 2(m + 1).
Demostración. Sea P la (w, y)-trayectoria más corta que une a w con y en G. Por (1),
existe una trayectoria P ′ de longitud m con vértice inicial y y vértice final yy ∈ S(y).
Además, los vértices internos de P ′ están contenidos en G − H, ya que si tuviera un
vértice x en 〈H〉G −S(y) se tiene que dG(y, x) ≤ m, lo cual contradice que dG(y, 〈H〉G −
S(y)) ≥ m + 1. Por lo tanto, los vértices interiores estan contenidos en G − H.
Afirmamos que la (w, y)-trayectoria pasa por 〈H〉G. Supongamos por contradicción
que la (w, y)-trayectoria no pasa por 〈H〉G, entonces el camino
(w, P, y) ∪ (y, P ′, yy) contiene una (w, S(y))-trayectoria cuyos vértices internos están
contenidos en G − H, lo que contradice (2). Por lo tanto, P pasa por 〈H〉G.
Sean z1 y z2 dos vértices en la (w, y)-trayectoria tal que z1 es el primer vértice
de la trayectoria que está en H y z2 el último vértice de la trayectoria que está en H.
Observemos que z1 está en 〈H〉G−S(y), pues es el primer vértice de la (w, y)-trayectoria
que está en H y por (2) sabemos que no existe una (w, S(y))-trayectoria cuyos vértices
internos estén en G − H.
Entonces tenemos dos casos.
Caso a) z1 6= z2. Tenemos que dG(w, y) = dG(w, z1) + dG(z1, z2) + dG(z2, y). Como
observamos que z1 en 〈H〉G − S(y), por (1) tenemos que dG(w, z1) ≥ m + 1. Además,
como z1 6= z2, dG(z1, z2) ≥ 1 y por (1) tenemos que dG(z2, y) ≥ m. Por lo tanto,
dG(w, y) ≥ 2(m + 1).
74 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Caso b) z1 = z2. Tenemos que dG(w, y) = dG(w, z1) + dG(z1, y). Como observamos
que z1 en 〈H〉G − S(y) tenemos que z1 = z2 en 〈H〉G − S(y). Por (1), dG(w, z1) ≥ m + 1
y dG(z1, y) ≥ m + 1. Por lo tanto, dG(w, y) ≥ 2(m + 1).
3.2. k-árboles m-dominantes en gráficas
A continuación, haremos la demostración del teorema para los k-árboles
m-dominantes en gráficas n-conexas.
Veremos en la primera parte de dicha demostración que efectivamente el
siguiente teorema es una generalización para el teorema de Broersma 3.0.1
y el teorema de árboles generadores con grados acotados propuesto por V.
Neumann y E. Rivera 2.2.1.
Teorema 3.2.1. [12] Sean k ≥ 2, n ≥ 1, m ≥ 0 tres enteros positivos y G una gráfica
n-conexa. Si α2(m+1)(G) ≤ (k − 1)n + 1, entonces G tiene un k-árbol que m-domina a
G.
Demostración. Observemos que la condición del Teorema 3.2.1 es
α2(m+1)(G) ≤ (k − 1)n + 1.
Si m = 0, entonces α2(G) ≤ (k − 1)n + 1, como sabemos que α2(G) es igual al número
de independencia tenemos la condición del Teorema 2.2.1 propuesto por V. Neumann
y E. Rivera. Como vimos anteriormente se encuentra un s + 1-árbol generador de G,
que 0-domina a G.
Si k = 2, entonces
α2(m+1)(G) ≤ n + 1,
esta condición es la que se tiene en el Teorema 3.0.1 propuesto por Broersma; en el que
se encuenta una trayectoria m-dominante en G; la cual es un 2-árbol que m-domina a
G.
Por lo tanto, supongamos que m ≥ 1 y k ≥ 3.
Sea G una gráfica n-conexa que satisface la condición del Teorema 3.2.1.
Demostraremos por contradicción, supongamos que G no tiene un k-árbol que m-
domine a G.
Como G es n-conexa, por la Observación 1.1 tenemos que n ≤ K(G) ≤ δ(G), por
lo que el grado mínimo en G es al menos n; por esto y por la Proposición 1.1 sabemos
que en G tenemos una trayectoria de longitud al menos n − 1. La cual es un 2-árbol.
Sea T ′ un k-árbol de G, que no m-domina a G, por lo anterior |V (T ′)| ≥ n.
Como T ′ no m-domina a G, existe un vértice w en G − Domim(T ′). Ahora como
G es n-conexa por el Teorema 1.11.2 sabemos que existen en G al menos n (w, T ′)-
trayectorias distintas, a las cuales denotaremos de la siguiente forma Q1, Q2, . . . , Qn tal
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 75
que para i en {1, 2, . . . , n} cada Qi conecta a w con vi un vértice de T ′, para toda i 6= j
se tiene que Qi ∩ Qj = {w} y para toda i se cumple que Qi ∩ T ′ = {vi}, denotemos por
V ∗ = {v1, v2, . . . , vn} al conjunto de vértices vi en T ′.
Figura 3.2: Visualización de las (w, V ∗)-trayectorias en G
Sean D1, D2, . . . , Dl las componentes conexas obtenidas de la gráfica T ′ − V ∗ y
D = {D1, D2, . . . , Dl}.
Definimos a ϑT ′(Di) = {v ∈ V ∗ : v ∈ NT ′(Di)} para cada Di en D. Por ello
ϑT ′(Di) consiste de vértices de V ∗ que son adyacentes a Di en T ′.
Sean
D
T ′
1 = D1 = {D ∈ D : |ϑT ′(D)| = 1}, D
T ′
2 = D2 = {D ∈ D : |ϑT ′(D)| = 2} y
D
T ′
≥3 = D≥3 = {D ∈ D : |ϑT ′(D)| ≥ 3}.
Figura 3.3: DT ′
1 , DT ′
2 y D
T ′
≥3
76 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Como no existe confusión abreviamos la notación D
T
∗ como D∗.
De todos los k-árboles posibles que no m-dominan a G tomemos a T un k-árbol,
w /∈ Domim(T ) un vértice y n (w, T )-trayectorias Q1, Q2, . . . , Qn tal que:
(a) |Domim(T )| sea máximo,
(b) |DT
1 ∪ DT
≥3| sea mínimo, sujeto a (a),
(c) |Hojas(T )| sea mínimo, sujeto a (b), y
(d) |V (T )| sea tan pequeño como sea posible, sujeto a (c).
Por la elección de T por (a), podemos obtener la siguiente afirmación.
Afirmación 3.2.1. δT (v) = k para todo v ∈ V ∗.
Demostración. Supongamos por contradicción que δT (v) ≤ k − 1 para algún vértice
v ∈ V ∗.
Tomemos a Q la trayectoria más corta que une a w con T , dicha trayectoria existe
por la n-conexidad de G. Como v ∈ V ∗ tenemos que la trayectoria Q cumple lo si-
guiente Q ∩ T = {v}, por ello la gráfica T + Q es un árbol, como δT +Q(v) ≤ k y el
grado máximo en T + Q es a lo más k, entonces T + Q es un k-árbol (observemos la
Figura 3.4). Entonces Domim(T ) ∪ {w} ⊆ Domim(T + Q) lo que contradice a (a), pues
|Domim(T )| es máximo.
Por lo tanto, δT (v) = k para todo v ∈ V ∗. ♦
Figura 3.4: T + Q
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 77
Afirmación 3.2.2. (i) Todo par de vértices en V ∗ son no adyacentes en T .
(ii) |D| = (k − 1)n + 1 y |DT
1 | = (k − 2)n +
∑
D∈DT
≥3
(|ϑT (D)| − 2) + 2.
Demostración. (i) Supongamos por contradicción que dos vértices va y vb de V ∗
son adyacentes en T . Observemos que las trayectorias Qa y Qb que conectan a w con
va y vb respectivamente, forman un ciclo Qa ∪ Qb ∪ vavb. Por lo que en la gráfica
T ′ = T + Qa + Qb − vavb tenemos un único ciclo y se aumenta en uno el grado de los
vértices va y vb, por el Teorema 1.9.5 al quitar la arista vavb se rompe el ciclo único
de T ′ y se reduce el grado en uno en ambos vértices. Por lo tanto, T ′ es una gráfica
acíclica, conexa y de grado máximo k, por lo que T ′ es un k-árbol de G que satisface
Domim(T ) ∪ {w} ⊆ Domim(T ′) lo que es contradice a (a). Por lo tanto, se cumple (i).
(ii) Por (i) sabemos que V ∗ es un conjunto independiente de T , del Lema 1.5 (ii)
se tienen que:
c(T − V ∗) =
∑
v∈V ∗
(δT (v) − 1) + 1
y de la Afirmación 3.2.1 tenemos que para todo v ∈ V ∗ δT (v) = k, entonces
c(T − V ∗) = |D| = (k − 1)n + 1.
Por otro lado, si contraemos cada una de las componentes de D a un único vértice y
lo hacemos adyacente con V ∗ se obtiene un árbol de componentes conexas TD a partir
de T . Entonces V (TD) = V ∗ ∪ D
T
1 ∪ D
T
2 ∪ D
T
≥3, donde cada componente de D
T
1 ; por
definición, corresponde a una hoja de TD.
Figura 3.5: Ejemplo de un árbol T , componentes conexas D y el árbol de componentes
conexas TD
78 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Por el Lema 1.5 el número de hojas de TD es:
|Hojas(TD)| =
∑
v∈W
(δT (v) − 2) + 2, W = {v ∈ V (T ) : δT (v) ≥ 3}.
Por la Afirmación 3.2.1 sabemos que para todo v vértice en V ∗ δT (v) = k, como
k ≥ 3 y D
T
≥3; tenemos que:
|DT
1 | =
∑
D∈DT
≥3
(δT (D) − 2) + 2
= (k − 2)n +
∑
D∈DT
≥3
(δT (D) − 2) + 2
= (k − 2)n +
∑
D∈DT
≥3
(|ϑT (D)| − 2) + 2. ♦
Afirmación 3.2.3. Para todo vértice x de grado 1 en T , existe un vértice
yx en Domim(T ) tal que dG(yx, x) = m y dG(yx, T − x) ≥ m + 1.
Demostración. Sean x una hoja de T y W = {y ∈ V (G) : dG(y, x) = m}.
Supongamos por contradicción que W = ∅ o dG(y, T − x) ≤ m para toda y ∈ W .
Si W = ∅, entonces no existe algún vértice yx en Domim(T ), por lo que se cumple que
Domim(T ) = Domim(T − x).
Como x es una hoja de T , x /∈ V ∗. Por demostrar que 〈{x}〉 no es una componente
conexa en D. Supongamos por contradicción que si es una componente conexa de D.
Sean vi el vértice en V ∗ tal que x es adyacente a vi y Qi la (w, vi)-trayectoria, entonces
T ′ = (T − x) + Qi es un k-árbol en G pues se tiene que δT ′(vi) = δT (vi) + 1 − 1, como
se muestra en la Figura 3.6, con Domim(T ) ∪ {x} ⊆ Domim(T ′), esto contradice a (a),
por lo que 〈{x}〉 no es una componente conexa en D.
Figura 3.6: T ′ = T − x + Qi
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 79
Supongamos que x ∈ Dl con 1 ≤ l ≤ n. Entonces por el Teorema 1.9.3 sabemos que
T − x es un k-árbol, como en G no tenemos un k-árbol que m-domine a G, entonces
tenemos un vértice w /∈ Domim(T − x). Tomemos a Q1, Q2, . . . , Qn las (w, T − x)-
trayectorias y {Dl − {x}} ∪ {Di : 1 ≤ i ≤ n, i 6= l} el conjunto de las componentes de
(T − x) − V ∗. Por lo tanto, |DT
1 ∪D
T
≥3| = |DT −x
1 ∪D
T −x
≥3 |, |Hojas(T )| > |Hojas(T − x)|
y |V (T )| > |V (T ) − {x}|, lo que contradice (c) y (d). Por lo tanto, existe un yx en W
tal que dG(yx, T − x) ≥ m + 1. ♦
De la Afirmación 3.2.3, se obtiene la siguiente afirmación.
Afirmación 3.2.4. Para todo par de hojas distintas x1 y x2 de T se tiene que yx1
6= yx2
.
Demostración. Supongamos por contradicción que yx1
= yx2
con x1 6= x2.
Por la Afirmación 3.2.3 tenemos que dG(yx1
, x1) = m y dG(yx2
, x2) = m. Además
dG(yx1
, x1) ≥ m + 1, como x2 ∈ V (T ) − x1, dG(yx1
= yx2
, x2) ≥ m + 1, lo que es una
contradicción pues dG(yx2
, x2) = m.
Por lo tanto, yx1
6= yx2
(observemos la Figura 3.7). ♦
Figura 3.7: dG(yx1
, x1) = m y dG(yx2
, x2) = m
Sea YHojas = {yx : x ∈ Hojas(T )}, para cada y ∈ YHojas definimos a S(y) como
S(y) = {x ∈ Hojas(T ) : yx = y}; el cual por la afirmación anterior consiste de un
vértice x ∈ Hojas(T ).
Por la elección de T y la condición (a) obtenemos la siguiente afirmación.
80 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Afirmación 3.2.5. Para todo vértice y ∈ YHojas no existe P una (w, S(y))-trayectoria
en G, tal que los vértices internos de P estén contenidos en G − T .
Demostración. Supongamos por contradicción que existe P una (w, S(y))-trayectoria
cuyos vértices interiores estén contenidos en G − T . Sabemos que como
w ∈ V (G) − Domim(T ), entonces podemos obtener a T ′ = T + P . Por demostrar
que T ′ es un k-árbol. Como P ∩ T = {x}, pues los vértices interiores de P están con-
tenidos en G − T , δT ′(x) = 2 y el grado de los vértices en P es menor o igual que 2,
entonces T ′ es un k-árbol. Además T ′ cumple que |Domim(T )| < |Domim(T ′)|, lo que
es una contradicción a (a).
Por lo tanto, los vértices internos de la (w, S(y))-trayectoria no pueden estar conte-
nidos en G − T . ♦
Figura 3.8: T ′ = T + P
Afirmación 3.2.6. Para todo par de vértices distintos y1 y y2 en YHojas∪{w} se cumple
que dG(y1, y2) ≥ 2(m + 1).
Demostración. Como y1 y y2 están en YHojas ∪ {w} tenemos dos casos:
Caso 1) Si y1 = w, entonces por la Afirmación 3.2.5 sabemos que no existe una
(w, S(y))-trayectoria cuyos vértices interiores estén contenidos en G − T y de la Afir-
mación 3.2.3 sabemos que dG(w, T − S(y)) ≥ m + 1, por ello se tienen las condiciones
del Lema 3.2, por lo tanto, dG(y1 = w, y2) ≥ 2(m + 1).
Caso 2) Si y1 y y2 son dos vértices en YHojas, entonces veremos que se cumplen las
condiciones (i) y (ii) del Lema 3.2.
Primero veamos que para i en {1, 2}. Sea S(yi) = {xi}, entonces por la Afirmación
3.2.3 dG(yi, xi) = m y dG(yi, T − xi) ≥ m + 1. Por lo que se cumple (i) del Lema 3.2.
Ahora veamos que se cumple la condición (ii) del Lema 3.2. Por demostrar que no
existe en G una (x1, x2)-trayectoria cuyos vértices interiores estén contenidos en G −
T . Supongamos por contradicción que existe P una (x1, x2)-trayectoria cuyos vértices
interiores están contenidos en G − T .
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 81
Veamos primero que para 1 ≤ i ≤ n P no intersecta a Qi. Supongamos por contra-
dicción que Qi intersecta a P . Sea u el primer vértice de P que intersecta a Qi, entonces
podemos obtener la siguiente trayectoria (x1, P, u) ∪ (u, Qi, w).
La cual es una (w, S(y))-trayectoria tal que sus vértices interiores están contenidos
en G − T , lo que es una contradicción a la Afirmación 3.2.5.
Ahora observemos que por el Teorema 1.9.5 existe en T , una única (x1, x2)-trayectoria,
a la que llamaremos P ′, lo que implica los siguientes casos P ′ ∩ V ∗ = ∅ o P ′ ∩ V ∗ 6= ∅.
Caso 2.1) Si P ′ ∩ V ∗ 6= ∅, entonces existe al menos un va en P ′ ∩ V ∗; tal que en
la gráfica T − V ∗ se tienen que para i en {1, 2} existen D1, D2 en D; tal que xi en Di.
Entonces T + P contiene un único ciclo C que pasa por el vértice va de V ∗. Sean e una
arista de C que incide en el vértice va, por el Teorema 1.9.5 T + P − e es conexa y
acíclica.
Consideremos a la trayectoria Qa que une a T con el vértice va. Tomemos a
T ′ = T + P + Qa − e, el cual por lo anterior es un árbol. Por demostrar que T ′ es
una k-árbol. Por definición de V ∗ sabemos que Qa ∩ T = {va}, por lo que δT (va) = k
y en T ′ se agrega la trayectoria Qa y se quita la arista e, entonces se cumple que
δT ′(va) = δT (va) = k, por lo tanto, T ′ es un k-árbol como se puede ver en la Figura 3.9.
Como T ′ es un k-árbol que Domim(T ) ∪ {w} ⊆ Domim(T ′) se contradice la condición
(a). Pues Domim(G) ⊂ Domim(T ′), lo que implica que |Domim(T )| < |Domim(T ′)|.
Figura 3.9: T ′ = T + P + Qa − e
82 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Caso 2.2) Si P ′ ∩ V ∗ = ∅, entonces existe una componente conexa D ∈ D tal que
{x1, x2} ⊆ V (D). Entonces la gráfica D + P contiene un ciclo C formado por P y P ′.
Ahora construiremos a T ′ un k-árbol a partir de T + P al borrar una arista en C que
incide en un vértice de grado al menos 3 en T , dicho vértice existe pues x1 y x2 no son
adyacentes, por lo que P ′ tiene al menos tres vértices. Tomemos a x un vértice en P ′
con x 6= x1 y x 6= x2, así se cumple que δT (x) ≥ 3 pues se tiene la (x, V ∗)-trayectoria.
Como e incide en v con δT (x) ≥ 3 y se cumple que δT ′(x) ≥ 2, T ′ es un k-árbol, como se
muestra en la Figura 3.10. Sea D′ = D + P − e. Sabemos que w /∈ Domim(T ′), por ello
se tiene que |Domim(T )| ≤ |Domim(T ′)|. Si se tiene que |Domim(T )| < |Domim(T ′)|,
entonces se contradice a (a). Si se tiene que |Domim(T )| = |Domim(T ′)|, entonces como
las Q1, Q2, . . . , Qn son (w, T ′)-trayectorias y que D′ = (D− {D}) ∪ {D′} es el conjunto
de componentes conexas de T ′−V ∗, se cumple que |D| = |D′|. Por lo tanto, tenemos que
|DT
1 ∪ D
T
≥3| = |DT ′
1 ∪ D
T ′
≥3| y |Hojas(T )| > |Hojas(T ′)|. Esto último contradice a (c).
Figura 3.10: T ′ = T + P + Qa − e
Por lo tanto, no existe en G una (x1, x2)-trayectoria cuyos vértices estén contenidos
en G − T . Así tenemos que también se cumple el inciso (ii) del Lema 3.2.
Por lo tanto, por el Lema 3.2 se cumple que dG(y1, y2) ≥ 2(m + 1). ♦
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 83
Afirmación 3.2.7. Existe una componente D∗ en D1 tal que para todo x ∈ V (D∗) se
cumple que δT (x) ≤ k − 1.
Demostración. Supongamos por contradicción que para todo x ∈ V (D) no existe
D ∈ D1 tal que δT (x) ≤ k − 1. Entonces, toda componente D ∈ D1 tiene al menos un
vértice de grado igual a k en T . Por el Corolario 1.2, D tiene al menos k hojas de T ,
pues existe un vértice x en D tal que δT (x) = k, como D ∈ D1, entonces tenemos al
menos k − 1 hojas de T en D.
De la Afirmación 3.2.6 sabemos que para {y1, y2} ⊆ YHojas dG(y1, y2) ≥ 2(m + 1),
por lo que α2(m+1)(G) ≥ |YHojas|.
De la Afirmación 3.2.4 sabemos que para cada x1 y x2 hojas distintas de T se tiene
que y1 6= y2, por lo que |YHojas| = |Hojas(T )|.
Ahora, como sabemos que Hojas(T ) ∩ V (D) ⊆ Hojas(T ), se tiene que
|Hojas(T )| ≥
∑
D∈D1
|Hojas(T ) ∩ V (D)|.
Como D tiene al menos k − 1 hojas de T tenemos que
∑
D∈D1
|Hojas(T ) ∩ V (D)| ≥ |D1|(k − 1).
De la Afirmación 3.2.2 sabemos que |D1| = (k − 2)n + 2, entonces
|D1|(k − 1) ≥ ((k − 2)n + 2)(k − 1)
((k − 2)n + 2)(k − 1) ≥ (n + 2)(k − 1) ≥ (k − 1)n + 2.
Por lo que, α2(m+1)(G) ≥ (k − 1)n + 2.
Lo que es una contradicción a la hipótesis para α2(m+1)(G) del Teorema 3.2.1. ♦
De las afirmaciones anteriores, podemos suponer sin pérdida de generalidad, que
D∗ = D1 y {v1} = ϑT (D1). Ahora veamos a T como un árbol con raíz en v1. Para cada
D ∈ D, sean rD la raíz de la componente D y r−
D = vD en V ∗ el vértice antecesor de
rD, donde la raíz de D no tiene vértice antecesor en D; es decir,
dG(v1, rD) < dG(v1, x) con x ∈ D \ {rD}.
Como V ∗ ⊆ T − D1 tenemos que el orden de T − D1 es mayor o igual que n. Como
G es n-conexa, por el Teorema 1.11.2 sabemos que existen al menos n (D1, T − D1)-
trayectorias R1, R2, . . . , Rn en G tal que toda trayectoria Ri conecta un vértice de D1
con T −D1, por el Teorema 1.11.2 para i 6= j los vértices finales de Ri y Rj son distintos
en T − D1.
84 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Observación. Los vértices interiores de cada Ri están contenidos en G − T .
Demostración. Supongamos por contradicción que Ri ∩ (T − D1) 6= ∅. Sabemos que
como T es árbol, por el Teorema 1.9.5 existe una única trayectoria entre todo par de
vértices de T . Entonces T +Ri contiene un único ciclo. Sea x el primer vértice de Ri en la
intersección. Si quitamos una arista adyacente a x en T obtenemos a T ′ = T +Ri −xx−,
la cual es una gráfica acíclica y conexa, como podemos observar en la Figura 3.11. Como
en D1 todos los vértices son de grado a lo más k − 1 al agregarle la trayectoria Ri a lo
más obtendríamos un nuevo vértice de grado k en T ′, por lo tanto, T ′ es un k-árbol que
cumple que |Domim(T )| = |Domim(T ′)|. Por otro lado al unir la trayectoria Ri a D1
tenemos que en T ′ D1 en D2. Por lo que |DT ′
1 ∩ D
T ′
≥3| < |DT
1 ∩ D
T
≥3|, lo que contradice
a (b). ♦
Figura 3.11: T ′ = T + Ri − xx−
En particular, Ri∩Rj ⊆ V (D1) y para toda i en {1, 2, . . . , n} |Ri∩D1| = 1. Observe-
mos que puede suceder que algún Rc consista de una arista rD1
v1. Para
1 ≤ i ≤ n, sea U∗ el conjunto de los vértices finales de Ri, los cuales están conte-
nidos en T − D1, por lo que |U∗| = n.
Afirmación 3.2.8. No existe una (w, D1)-trayectoria tal que sus vértices interiores
están contenidos en G − T . En particular, para toda 1 ≤ i y j ≤ n tenemos que
V (Qi) ∩ V (Rj) ⊆ {vi}.
Demostración. Supongamos por contradicción que existe Q una (w, D1)-trayec- toria
tal que sus vértices interiores están contenidos en G−T . Sea T ′ = T +Q como se muestra
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 85
en la Figura 3.12. Como los vértices interiores de Q están en G − T |Q ∩ T | = 1 y para
todo v ∈ D1 el grado de v es a lo más k − 1 (Afirmación 3.2.7), entonces T ′ es un
k-árbol que satisface que Domim(T ) ∪ {w} ⊆ Domim(T ′), lo que es una contradicción
a (a). Pues Domim(G) ⊂ Domim(T ′), lo que implica que |Domim(T )| < |Domim(T ′)|.
Figura 3.12: T ′ = T + Q
Observemos que para toda 1 ≤ i y j ≤ n tenemos que V (Qi) ∩ V (Rj) ⊆ {vi}. Su-
pongamos por contradicción que |V (Qi) ∩ V (Rj)| ≥ 2, entonces tenemos una (w, D1)-
trayectoria formada por (v, Rj, x) ∪ (x, Qi, w) para v ∈ D1 y con x 6= vi el primer
vértice de Rj en la intersección con Qi, lo que es una contradicción a la Afirmación
3.2.8, pues la (w, D1)-trayectoria obtenida tiene vértices contenidos en G − T . Por lo
tanto, V (Qi) ∩ V (Rj) ⊆ {vi}. ♦
Afirmación 3.2.9. Para todo u ∈ U∗ se cumple que δT (u) = k.
Demostración. Supongamos por contradicción que para algún u ∈ U∗ se cumple que
δT (u) ≤ k − 1. Sea Ra la trayectoria que conecta a D1 con u para 1 ≤ a ≤ n. Por la
afirmación 3.2.1 sabemos que para toda v ∈ V ∗ δT (v) = k, por lo que u 6= v1, pues
δT (u) ≤ k − 1. Tomemos a T ′ = (T + Q1 + Ra) − v1rD1
. Por demostrar que T ′ es un
k-árbol. Por la Afirmación 3.2.7 sabemos que todo vértice en D1 es de grado a lo más
k −1, por lo que al agregar la trayectoria Ra se tiene a lo más un nuevo vértice de grado
a lo más k. Ahora, por la Afirmación 3.2.1 sabemos que δT (v1) = k, por lo que al agrega
la trayectoria Q1 tenemos que el grado de v1 es k +1, pero tambíen estamos quitando la
arista v1rD1
, por lo tanto, tenemos que δT ′(v1) = k. Por la construcción de Ra y por la
Afirmación 3.2.8 sabemos que Ra ∩ Q1 ⊆ {vi} y que no existe una (w, D1)-trayectoria
que tenga vértices interiores en G − T ; T ′ es conexa y acíclica, como podemos observar
en la Figura 3.13.
86 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Figura 3.13: T ′ = (T + Q1 + Ra) − v1rD1
Por lo tanto, T ′ es un k-árbol tal que Domim(T )∪{w} ⊆ Domim(T ′), esto contradice
a (a). ♦
Afirmación 3.2.10. Para toda D ∈ D≥3 = D
T
≥3, se tiene que U∗ ∩ ϑT (D) ⊆ {vD}.
Demostración. Supongamos por contradicción que para alguna D ∈ D≥3 existe un
vértice u ∈ U∗ ∩ (ϑT (D) − {vD}). Sea Ra la trayectoria que conecta a D1 con u para
1 ≤ a ≤ n. Sea T ′ = (T + Ra) − uu− una nueva gráfica y consideremos a la componente
D′
1 = D1 + (Ra − {u}). Por el Teorema 1.9.5 T ′ es conexa y acíclica y por la Afirmación
3.2.7 para x ∈ D1 δT (x) ≤ k − 1, entonces para x ∈ D′
1 se cumple que δT ′(x) ≤ k, por
lo tanto T ′ es un k-árbol como se muestra en la Figura 3.14.
Figura 3.14: T ′ = (T + Ra) − uu−
Por la elección de T , por (a), w /∈ Domim(T ′). Sabemos por la Afirmación 3.2.8
que las (w, T ′)-trayectorias Q1, Q2, ..., Qn cumplen que Ra ∩ Qi ⊆ {vi} para i en
{1, 2, ..., n} y D′
1, D2, . . . , Dl son componentes conexas de T ′ − V ∗. Por
lo tanto, tenemos que |Domim(T )| ≤ |Domim(T ′)|. Si se tiene que
|Domim(T )| < |Domim(T ′)|, entonces se contradice (a). Si se cumple que
|Domim(T )| = |Domim(T ′)| y como se tiene que, |ϑT ′(D′
1)| = |ϑT (D1)| + 1 = 2,
|ϑT ′(D)| = |ϑT (D)| − 1 ≥ 2 y |ϑT ′(Di)| = |ϑT (Di)| para todo Di en D − {D1, D},
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 87
entonces |DT
1 ∪ D
T
≥3| < |DT ′
1 ∪ D
T ′
≥3|, lo que es una contradicción a (b). ♦
Afirmación 3.2.11. |V ∗ ∪ U∗| ≥ |V ∗| +
∑
D∈D≥3
(ϑT (D) − 1).
Demostración. Primero debemos construir un nuevo árbol a partir de T al que
llamaremos T ∗. Quitemos de T todas las componentes de D1, como ϑT (D) = 1 para
D ∈ D1 tenemos que T ′ = T −D1 es conexa y acíclica, como se muestra en la siguiente
Figura 3.15.
Figura 3.15: T ′ = T − D1 con {D1, D2, D3, ..., Ds} ⊆ D1
Sea |D2| = l. Para toda componente Di en D2 consideramos a T ′′ = T ′ − D2 ∪ S
con S =
⋃
Di∈D2
r−
Di
sDi
el conjunto de aristas entre los vértices {r−
Di
, sDi
} ⊆ ϑT (Di)
para toda i en {1, 2, ..., l}, como tenemos una arista que une a r−
D con sD para cada
componente en D2, T ′′ es conexa y acíclica, como se observa en la siguiente Figura 3.16.
Figura 3.16: T ′′ = T ′ − D2 ∪ S donde S =
⋃
Di∈D2
r−
Di
sDi
es el conjunto de aristas entre
los vértices {r−
Di
, sDi
} ⊆ ϑT (Di) para toda i en {1, 2, ..., l}
88 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Sea |D≥3| = p. En el árbol T ′′ para toda i en {1, 2, ..., p} contraemos a cada com-
ponente Di en D≥3 a un vértice di tal que tenemos las aristas divj con vj en ϑT (Di)
que cumplen que |ϑT (Di)| = δT ∗(di) para toda i en {1, 2, ..., p}. Llamamos a este nuevo
árbol como T ∗, por construcción T ∗ es conexa y acíclica como se muestra en la siguiente
Figura 3.17.
Figura 3.17: T ∗ donde {vD2
, v′
D2
, vD3
, v′
D3
} ⊆ V ∗
Usemos la misma notación del conjunto de componentes D≥3 para conjunto de
vértices di. Entonces el conjunto de vértices de T ∗ es V ∗ ∪ D≥3. Consideremos a T ∗
como un árbol con raíz en v1. Entonces para todo vértice di, tenemos |ϑT (di)| − 1
vértices hijos de di en T ∗. Por la Afirmación 3.2.10, estos vértices hijos de di están
contenidos en V ∗ − (U∗ ∩ V ∗). Como |U∗| = |V ∗| = n, tenemos que:
|U∗ − (V ∗ ∩ U∗)| = |V ∗ − (U∗ ∩ V ∗)| ≥
∑
D∈D≥3
(ϑT (D) − 1).
Por lo tanto, tenemos que:
|V ∗ ∪ U∗| = |V ∗| + |U∗ − (V ∗ ∩ U∗)| ≥ |V ∗| +
∑
D∈D≥3
(ϑT (D) − 1). ♦
Ahora, para facilitar la demostración es necesario introducir notación adicional.
Denotamos por P [s, t] una trayectoria en T que conecta a dos vértices s y t y por:
1. P (s, t) a la subtrayectoria de P [s, t] tal que {s, t} * V (P (s, t)).
2. P [s, t) a la subtrayectoria de P [s, t] tal que s ∈ V (P [s, t)) y t /∈ V (P [s, t)).
3. P (s, t] a la subtrayectoria de P [s, t] tal que s /∈ V (P [s, t)) y t ∈ V (P [s, t)).
Para cada D ∈ D2, sea ϑT (D) = {vD = r−
D, sD}, donde rD es la raíz de D.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 89
Si D ∈ D2 posee alguna de las siguientes tres propiedades, entonces D será llamada
componente pseudotrayectoria:
(e) rD = s−
D, D = {rD} y δT (s−
D = rD) = 2.
(f) D es una trayectoria, rD 6= s−
D y δT (rD) = δT (s−
D) = 2.
(g) Existe un vértice zD en P [rD, s−
D] tal que zD en U∗ y δT (z) = 2 para todo vértice
z ∈ P (zD, s−
D], donde P (zD, s−
D] = ∅ si rD = s−
D.
Sea DP
2 = {D ∈ D2 = D
T
2 : D es componente pseudotrayectoria}.
Afirmación 3.2.12. Si D ∈ DP
2 , entonces existe un vértice xD en P [rD, s−
D] que satis-
face las siguientes dos propiedades, donde P (xD, s−
D] = ∅.
(i) δT (z) = 2 para todo vértice z ∈ P [xD, s−
D].
(ii) Domim(P [xD, s−
D]) ⊆ Domim(T − P [xD, s−
D]).
Demostración. Si δT (s−
D) = 2, entonces tomemos xD = s−
D, por lo que δT (z) = 2
para toda z ∈ P [xD, s−
D] = {s−
D}; es decir, que se cumple (i).
Como P (xD, s−
D] = ∅, entonces Domim(P [xD, s−
D]) ⊆ Domim(T − P (xD, s−
D)). Por
lo tanto, se cumple (ii).
Observemos que si D ∈ DP
2 tal que cumple con (e), entonces tenemos que δT (s−
D) = 2
y si D ∈ DP
2 tal que cumple con (f), entonces δT (s−
D) = 2.
Por lo que asumimos que D satisface (g) y como P [xD, s−
D] = ∅ tenemos que
zD = s−
D. Tomemos a Qr−
D
la (r−
D, w)-trayectoria, QsD
la (sD, w)-trayectoria y RzD
la (D1, zD)-trayectoria. Por la Afirmación 3.2.8 se cumple que RzD
∩ QrD
= ∅ y
RzD
∩ QsD
= ∅. Consideremos a T ′ = (T + QrD
+ QsD
) − r−
DrD, por el Teorema 1.9.5
es conexa y acílcica, por lo que es un árbol. Además, observemos que como {r−
D} ⊆ V ∗
y en T ′ se agregan las trayectorias Qr−
D
y QsD
y se quita la arista r−
DrD, se tiene que,
δT ′(r−
D) = k y δT ′(sD) = k + 1. Ahora consideremos a T ′′ = (T ′ + RzD
) − sDs−
D, el cual
nuevamente por el Teorema 1.9.5 es un árbol. Finalmente debemos demostrar que T ′′
es un k-árbol; como zD en U∗ por la Afirmación 3.2.9; δT (zD) = k, por otro lado te-
nemos que δT ′′(zD) = δT (zD) + 1 − 1 = k + 1 − 1, δT ′′(sD) = δT ′(sD) − 1 = k y por la
Afirmación 3.2.7 tenemos que para todo vértice x ∈ D1 δT (x) ≤ k − 1, por lo que
δT ′′(x) ≤ k. Por lo tanto, T ′′ es un k-árbol como se muestra en la Figura 3.18, que
Domim(T ) ∪ {w} ⊆ Domim(T ′′), lo que es una contradicción a (a). ♦
Figura 3.18: T ′′ = (T ′ + RzD
) − sDs−
D
90 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Para cada D ∈ DP
2 , tomemos un vértice xD en P [xD, s−
D] tal que satisface las pro-
piedades de la Afirmación 3.2.12 de modo que el orden de P [xD, s−
D] sea tan grande
como sea posible.
Afirmación 3.2.13. Si D ∈ DP
2 , entonces existe un vértice yD tal que:
dG(yD, P [xD, s−
D]) = m y dG(yD, T − P [xD, s−
D]) ≥ m + 1.
Demostración. Sea W = {y ∈ V (G) : dG(y, P [xD, s−
D]) = m}. Supongamos por con-
tradicción que o bien W = ∅ o que para toda y ∈ W tenemos que
dG(y, T − P [xD, s−
D]) ≤ m. Tomemos a Qr−
D
la (r−
D, w)-trayectoria y QsD
la (sD, w)-
trayectoria.
Primero, supongamos que D que cumple con la condición (e). Consideremos a
T + Qr−
D
+ QsD
, la cual contiene un único ciclo, por el Teorema 1.9.5
T ′ = T + Qr−
D
+ QsD
− s−
DsD es un árbol, como se muestra en la Figura 3.19. Como
δT ′(rD = s−
D) = δT (rD = s−
D) − 1 = 2 − 1, entonces por el Teorema 1.9.3
T ′′ = T ′ − (rD = s−
D) es un árbol, como podemos observar en la Figura 3.19. Ade-
más, se cumple que δT ′(r−
D) = δT (r−
D) + 1 − 1 y δT ′(sD) = δT (sD) + 1 − 1, por lo que T ′′
es un k-árbol que satisface Domim(T ) ∪ {w} ⊆ Domim(T ′′), lo que contradice a (a).
Figura 3.19: T , T ′ = T + Qr−
D
+ QsD
y T ′′ = T ′ − (rD = s−
D)
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 91
Ahora supongamos que D satisface la condición (f). Si xD 6= rD, entonces el
vértice x−
D cumple que δT (x−
D) = 2 pues D es una trayectoria y satisface las pro-
piedades (i) y (ii) de la Afirmación 3.2.12, lo que contradice la elección de xD pues
tenemos que |V (P [x−
D, s−
D])| > |V (P [xD, s−
D])|. Por lo tanto, xD = rD. Tomemos a
T ′ = (T + Qr−
D
+ QsD
) − P [rD, s−
D]. Sabemos que como {r−
D, sD} ⊆ V ∗ y como P [rD, s−
D] ∼=
D se cumple que para todo v en V (P [rD, s−
D]) δT (v) = 2 δT ′(r−
D) = δT (r−
D) + 1 − 1 y
δT ′(sD) = δT (sD) + 1 − 1, por lo tanto, T ′ es un k-árbol (ver Figura 3.20) que satisface
Domim(T ) ∪ {w} ⊆ Domim(T ′), lo que contradice a (a).
Finalmente supongamos que D satisface la condición (g). Si xD /∈ Hijos(zD), enton-
ces el vértice x−
D cumple que δT (x−
D) = 2; pues todo v en la subtrayectoria V (P (zD, s−
D])
cumple que δT (v) = 2, por lo que x−
D satisface las propiedades de la Afirmación 3.2.12,
lo que contradice la elección de xD, pues tenemos que |V (P [x−
D, s−
D])| > |V (P [xD, s−
D])|.
Por lo tanto, xD en Hijos(zD). Tomemos a RzD
la (zD, D1)-trayectoria. Consideremos
a T ′ = (T + Qr−
D
+ QsD
) − r−
DrD, por el teorema 1.9.5 T ′ es un árbol (ver Figura 3.20)
y además tenemos que δT ′(r−
D) = δT (r−
D) + 1 − 1 y δT ′(sD) = δT (sD) + 1. Tomemos a
T ′′ = (T + RzD
) − P [xD, s−
D], el cual por el Lema 1.3 es un árbol como se muestra en
la Figura 3.20, ya que T ′′ tiene un único ciclo y tenemos que todo x ∈ V (P [xD, s−
D]) se
cumple que δT (x) = 2. Sabemos que δT ′′(sD) = δT ′(sD) − 1 = k y por la Afirmación
3.2.7 tenemos que para todo vértice x ∈ D1 δT (x) ≤ k − 1, por lo que δT ′′(x) ≤ k. Por
lo tanto, T ′′ es un k-árbol que Domim(T )∪{w} ⊆ Domim(T ′′), lo que contradice a (a).
Figura 3.20: T ′ = (T + Qr−
D
+ QsD
) − r−
DrD y T ′′ = (T + RzD
) − P [xD, s−
D]
Por lo tanto, existe yD en W tal que dG(yD, P [xD, s−
D]) = m y
dG(yD, T − P [xD, s−
D]) ≥ m + 1. ♦
92 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Sea YT ray = {yD : D ∈ D
P
2 }. Para cada y ∈ YT ray, tomamos a D ∈ D
P
2 tal que
yD = y y sea S(y) = V (P [xD, s−
D]).
Afirmación 3.2.14. YHojas ∩YT ray = ∅ y para {D1, D2} ⊆ D
P
2 se tiene que yD1
6= yD2
.
Demostración. Supongamos por contradicción que YHojas ∩YT ray 6= ∅. Sea y el vérti-
ce en YHojas∩YT ray. Por definición de YT ray para y ∈ YT ray existe un S(y) = V (P [xD, s−
D]),
por la Afirmación 3.2.12 para todo vértice z en V (P [xD, s−
D]) se cumple que δT (z) = 2,
por la Afirmación 3.2.13 sabemos que
dG(y, P [xD, s−
D]) = m y dG(y, T − P [xD, s−
D]) ≥ m + 1. Como y ∈ YHojas por definición
de YHojas y por la Afirmación 3.2.3 existe un vértice x en Hojas(T ) tal que dG(y, x) = m
y dG(y, T − x) ≥ m + 1. Veamos los siguientes dos casos:
Caso 1) Si D cumple (f) o (g), entonces se tiene lo siguiente: Como
x ∈ Hojas(T ) se cumple que x /∈ V (P [xD, s−
D]). Por lo tanto, x ∈ T − V (P [xD, s−
D]).
Por la Afirmación 3.2.3 tenemos que dG(y, T − P [xD, s−
D]) ≤ dG(y, x) = m, lo que es
una contradicción.
Caso 2) Si D cumple (e), entonces se tiene lo siguiente: Como x ∈ Hojas(T ) se
cumple que x 6= rD. Por lo tanto, x ∈ T −rD. Entonces por la Afirmación 3.2.3 tenemos
que dG(y, T − rD) ≤ dG(y, x) = m, lo que es una contradicción.
Por lo tanto,
YHojas ∩ YT ray = ∅.
Por demostrar que yD1
6= yD2
para {D1, D2} ⊆ D
P
2 . Supongamos por contradicción
que yD1
= yD2
para D1 6= D2. Nuevamente tenemos dos casos:
Caso 1) Si D cumple (f) o (g), entonces se cumple lo siguiente:
Como {yD1
= yD2
} ⊆ YT ray, por la Afirmación 3.2.13
dG(yD1
, T − P [xD1
, s−
D1
]) ≥ m + 1
y como tenemos que V (P [xD2
, s−
D2
]) ⊆ T −V (P [xD1
, s−
D1
]) llegamos a una contradicción
pues dG(yD1
, P [xD2
, s−
D2
]) = m.
Caso 2) Si D cumple (e), entonces se tiene lo siguiente:
Por la Afirmación 3.2.13 tenemos que dG(yD1
, rD) ≥ m + 1; pero se cumple que
V (P [xD2
, s−
D2
]) ⊆ T−rD, lo que es una contradicción pues sabemos que dG(yD1
, P [xD2
, s−
D2
]) =
m.
Por lo tanto yD1
6= yD2
. ♦
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 93
Afirmación 3.2.15. Para y ∈ YT ray los siguientes enunciados son verdaderos:
(i) No existe una (w, S(y))-trayectoria cuyos vértices interiores estén contenidos en
G − T .
(ii) No existe una (D1, S(y))-trayectoria cuyos vértices interiores estén contenidos
en G − T .
Demostración. (i) Por demostrar que no existe una (w, S(y))-trayectoria cuyos vér-
tices interiores estén contenidos en G − T . Supongamos por contradicción que existe Q
una (w, S(y))-trayectoria cuyos vértices interiores están contenidos en G−T . Tomemos
a D ∈ D
P
2 y una trayectoria (sD, w)-trayectoria QsD
, tal que yD = y y sD en QsD
.
Afirmamos que la componente D cumple la condición (g) ya que si satisface (e)
o (f) se tiene que T + Q es un k-árbol, ver la Figura 3.21, donde se cumple que
Domim(T ) ∪ {w} ⊆ Domim(T + Q) y esto es una contradicción a (a).
Figura 3.21: T + Q
Sea z el vértice final de la trayectoria Q tal que está en S(y). Tomemos un vértice
w0 en Q ∩ QsD
tal que es el vértice de Q ∩ QsD
más cercano a z en Q. Consideremos a
94 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
T ′ = (T + QsD
+ Q[w0, z]) − P (z, s−
D]. Por la Afirmación 3.2.12, la elección de w0, por
el Teorema 1.9.5 y el Lema 1.3 T ′ es conexa y acíclica, por lo tanto, T ′ es un árbol,
observemos la Figura 3.22. Como δT ′(sD) = δT (sD)+1−1 y δT ′(sD) = δT (sD)+1 = 2+1,
entonces el grado máximo en T ′ es k. Por lo tanto, T ′ es un k-árbol que cumple que
Domim(T ) ∪ {w} ⊆ Domim(T ′), lo que contradice a (a).
Figura 3.22: T ′ = (T + QsD
+ Q[w0, z]) − P (z, s−
D]
(ii) Supongamos por contradicción que existe Q una (D1, S(y))-trayectoria cuyos
vértices interiores están contenidos en G − T . Tomemos a D ∈ D
P
2 y las trayec-
torias Qr−
D
y QsD
, tal que yD = y, r−
D en Qr−
D
y sD en QsD
. Notemos que por la
Afirmación 3.2.8 Q no intersecta a Qr−
D
ni a QsD
. Consideremos a
T ′ = (T + Qr−
D
+ QsD
+ Q) − r−
DrD − sDs−
D, el cual por el Teorema 1.9.5 y el Le-
ma 1.3 es conexa y acíclica, por lo tanto, T ′ es un árbol, veamos la Figura 3.23. Como
δT ′(sD) = δT + 1 − 1, δT ′(r−
D) = δT (r−
D) + 1 − 1 y por la Afirmación 3.2.7 sabemos que
δT (x) ≤ k + 1 para todo vértice x ∈ D1, por lo que se tiene que δT ′(x) ≤ k para todo
x ∈ V (T ′). Por lo tanto, T ′ es un k-árbol tal que Domim(T ) ∪ {w} ⊆ Domim(T ′), lo
que contradice a (a). ♦
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 95
Figura 3.23: T ′ = (T + Qr−
D
+ QsD
+ Q) − r−
DrD − sDs−
D
Afirmación 3.2.16. Para dos vértices distintos {y1, y2} ⊆ YHojas ∪ YT ray ∪ {w}, se
cumple que dG(y1, y2) ≥ 2(m + 1).
Demostración. Para i en {1, 2}, si yi en YHojas ∪ YT ray, entonces
dG(yi, S(yi)) = m y por las Afirmación 3.2.3 sabemos que si yi en YHojas, entonces
tenemos que dG(yi, T − S(yi)) ≥ m + 1. Por la afirmación 3.2.13 para i en {1, 2}, si yi
en YT ray tenemos que dG(yi, T − S(yi)) ≥ m + 1.
Supongamos que y1 = w. Por la Afirmación 3.2.5 sabemos que si y2 en YHojas,
entonces no existe una (w, S(y2))-trayectoria tal que sus vértices estén contenidos en
G − T y por la Afirmación 3.2.15 si y2 en YT ray, entonces no existe una (w, S(y2))-
trayectoria tal que sus vértices estén contenidos en G − T . Por lo anterior tenemos las
condiciones (i) y (ii) del Lema 3.2, por lo que se tiene que dG(w, y2) ≥ 2(m + 1).
Por lo tanto, supongamos que {y1, y2} ⊆ YHojas ∪ YT ray. Por lo visto al inicio de
está demostración ya contamos con la condición (i) del Lema 3.1, por lo que basta con
probar que no existe una (S(y1), S(y2))-trayectoria tal que sus vértices interiores estén
contenidos en G − T ; la cual es la condición (ii) del Lema 3.1. Por lo que debemos
considerar los siguientes tres casos:
96 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Caso (a) {y1, y2} ⊆ YHojas. Este caso ya se demostró en la Afirmación 3.2.6.
Caso (b) y1 en YHojas y y2 en YT ray.
Tomemos un vértice x ∈ Hojas(T ) y una componente D ∈ D
P
2 de modo que
S(y1) = {x} y S(y2) = V (P [xD, s−
D]). Supongamos por contradicción que existe una
(S(y1), S(y2))-trayectoria Q tal que sus vértices interiores están contenidos en G − T .
Sea z el vértice final de Q en S(y2). Tomemos ahora a Qr−
D
y a QsD
dos trayectorias
tales que r−
D en Qr−
D
y sD en QsD
. Por la Afirmación 3.2.8, sabemos que Q no intersecta
a Qr−
D
ni a QsD
.
Supongamos en primer lugar que x ∈ V (D). Si D satisface (e) o (f), D no tie-
ne vértices de grado uno en T , entonces D satisface la propiedad (g). Tomemos la
(D1, T − D1)-trayectoria RzD
tal que zD en RzD
. Por la Afirmación 3.2.8, RzD
no inter-
secta a Qr−
D
ni a QsD
. Por la Afirmación 3.2.15, RzD
tampoco intersecta a Q. Conside-
remos a T ′ = (T +Qr−
D
+QsD
+Q+RzD
)−P (zD, sD)−r−
DrD −zDz∗; donde zDz∗ es una
arista de la trayectoria PT (zD, x). Por el Lema 1.3 y el teorema 1.9.5, T ′ es un árbol
como se muestra en la Figura 3.24. Como tenemos que δT ′(zD) = δT (zD) + 1 = 2 + 1,
δT ′(r−
D) = δT ′(r−
D) + 1 − 1, δT ′(sD) = δT (sD) + 1 − 1 y por la Afirmación 3.2.7 sabe-
mos que para todo vértice v ∈ D1 se tiene que δT (v) ≤ k − 1, por lo que, se tiene
que δT ′(v) ≤ k para todo v ∈ V (T ′). Por lo tanto, T ′ es un k-árbol que cumple que
Domim(T ) ∪ {w} ⊆ Domim(T ′), lo que contradice a (a).
Figura 3.24: T ′ = (T + Qr−
D
+ QsD
+ Q + RzD
) − P (zD, sD) − r−
DrD − zDz∗
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 97
Supongamos ahora que x /∈ V (D), entonces construimos a T ′ a partir de T de la
siguiente manera T ′ = (T + Qr−
D
+ QsD
+ Q) − P (zD, sD) − r−
DrD, el cual por el Lema
1.3 y el Teorema 1.9.4 es un árbol, como se observa en la Figura 3.25. Además tenemos
que:
δT ′(zD) = δT (zD) + 1 = 2 + 1,
δT ′(r−
D) = δT ′(r−
D) + 1 − 1
y δT ′(sD) = δT (sD) + 1 − 1.
Por lo tanto, T ′ es un k-árbol tal que Domim(T ) ∪ {w} ⊆ Domim(T ′), lo que
contradice a (a).
Figura 3.25: T ′ = (T + Qr−
D
+ QsD
+ Q) − P (zD, sD) − r−
DrD
98 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Caso (c) {y1, y2} ⊆ YT ray.
Tomemos dos componentes {Da, Db} ⊆ D
P
2 , tal que yDa
= y1 y yDb
= y2 y a QsDa
,
QsDb
y Qr−
Da
tres trayectorias tales que sDa
en QsDa
, sDb
en QsDb
y r−
Da
en Qr−
Da
.
Primero supongamos por contradicción que existe Q una (S(y1), S(y2))-trayectoria
tal que sus vértices internos están contenidos en G − T . Sean za en S(ya) y zb en
S(yb) dos vértices tal que son vértices finales de Q. Si Da satisface (e) o (f), entonces
consideremos a
T ′ = T + QsDa
+ Qr−
Da
+ QsDb
+ Q − P (zb, sDb
) − sDa
s−
Da
− r−
Da
rDa
el cual por el Lema 1.3 y el Teorema 1.9.5 es un árbol, como se observa en la Figura
3.26. Además cumple que:
δT ′(sDa
) = δT (sDa
) + 1 − 1,
δT ′(sDb
) = δT (sDb
) + 1 − 1
y δT ′(r−
Da
) = δT (r−
Da
) + 1 − 1.
Por lo tanto, T ′ es un k-árbol que cumple que Domim(T ) ∪ {w} ⊆ Domim(T ′), lo
que contradice a (a).
Figura 3.26: T ′ = T + QsDa
+ Qr−
Da
+ QsDb
+ Q − P (zb, sDb
) − sDa
s−
Da
− r−
Da
rDa
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 99
Supongamos ahora que Da y Db satisfacen (g). Tomemos a Q una trayectoria tal
que |V (P (za, sDa
))| + |V (P (zb, sDb
))| sea tan pequeña como sea posible.
Consideremos un vértice u ∈ Domim(P (za, sDa
) ∪ P (zb, sDb
)) tal que
u /∈ Domim(T − (P (za, sDa
) ∪ P (zb, sDb
))), dicho vértice existe pues tenemos la trayec-
toria que une a YT ray con T . Sabemos que existe una (u, P (za, sDa
))-trayectoria cuyos
vértices interiores están contenidos en (G − T ) ∪ P (zb, sDb
) o existe una (u, P (zb, sDb
))-
trayectoria cuyos vértices interiores están contenidos en
(G − T ) ∪ P (za, sDa
). Por lo que, V (P [ua, sDa
]) ⊂ V (P [za, sDa
]) o
V (P [u, sb]) ⊂ V (P [zDb
, sDb
]), lo que implica que existe una (P (za, sDa
), P (zb, sDb
))-
trayectoria (u, P [u, za], za) ∪ (za, Q, zb) o (u, P [u, zb], zb) ∪ (zb, Q, za) cuyos vértices in-
teriores están contenidos en G − T , lo que contradice el hecho de que Q sea tan
pequeña como sea posible. Por lo tanto, por la Afirmación 3.2.12 (ii) tenemos que
Domim(P (za, sDa
)) ∪ P (zb, sDb
) ⊆ Domim(T − (P (za, sDa
) ∪ P (zb, sDb
))).
Consideremos a
T ′ = T + QDa
+ QDb
+ Qr−
Da
+ Q − P (zb, sDb
) − P (zDa
, sDa
) − r−
Da
rDa
,
por el Lema 1.3 y el Teorema 1.9.5 T ′ es un árbol. Además se cumple que
δT ′(sDa
) = δT (sDa
) + 1 − 1, δT ′(sDb
) = δT (sDb
) + 1 − 1, δT ′(r−
Da
) = δT (r−
Da
) + 1 − 1 y
por el hecho anterior concluimos que T ′ es un k-árbol tal que
Domim(T ) ∪ {w} ⊆ Domim(T ′); observemos la Figura 3.27, lo que contradice a (a).
Figura 3.27: T ′ = T + QDa
+ QDb
+ Qr−
Da
+ Q − P (zb, sDb
) − P (zDa
, sDa
) − r−
Da
rDa
100 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Por lo tanto, para los casos (a), (b) y (c) tenemos que se cumple el inciso (ii) del
Lema 3.1.
Por lo tanto, para dos vértices distintos {y1, y2} ⊆ YHojas ∪ YT ray ∪ {w}, se cumple
que dG(y1, y2) ≥ 2(m + 1). ♦
Afirmación 3.2.17. (i) Si D ∈ D
P
2 , entonces |Hojas(T )∩V (D)| ≥ (k−2)|U∗∩V (D)|.
(ii) Si D ∈ D2 − D
P
2 , entonces |Hojas(T ) ∩ V (D)| ≥ (k − 2)|U∗ ∩ V (D)| + 1.
(iii) |Hojas(T ) ∩
⋃
D∈D1
V (D)| ≥ (k − 2)|U∗ ∩
⋃
D∈D1
V (D)| + (k − 2)|V ∗| +∑
D∈D≥3
(|ϑT (D)| − 2) + 2.
(iv) Si D ∈ D≥3, entonces |Hojas(T ) ∩ V (D)| ≥ (k − 2)|U∗ ∩ V (D)| + |ϑT (D)| + 2.
Demostración. Observemos lo siguiente:
(I) Por un lado tenemos que:
Hojas(T ) ∩ V (D = {v ∈ V (T ) : δT (v) = 1} ∩ {V (D)} = {v ∈ V (D) : δT (v) = 1}.
Por otro lado tenemos que:
Hojas(T ) ∩ Hojas(D) = {v ∈ V (T ) : δT (v) = 1} ∩ {v ∈ V (D) : δD(v) = 1}
= {v ∈ V (D) : δT (v) = 1 y δD(v) = 1} = {v ∈ V (D) : δT (v) = 1}.
Por lo tanto, Hojas(T ) ∩ V (D) = Hojas(T ) ∩ Hojas(D).
(II) Por el Lema 1.5 sabemos que:
|Hojas(D)| =
∑
v∈W
(δD(v) − 2) + 2, donde W = {v ∈ V (D) : δD(v) ≥ 3},
∑
v∈W
(δD(v) − 2) + 2 =
∑
v∈V (D)
máx{δD(v) − 2, 0} + 2
=
∑
v∈V (D)\U∗
máx{δD(v) − 2, 0} + 2 +
∑
v∈V (D)∩U∗
máx{δD(v) − 2, 0}.
Ahora, procedamos a la demostración de cada inciso.
(i) Sea D ∈ D
P
2 . Si D cumple con (e) o (f), entonces
U∗ ∩ V (D) = ∅ y Hojas(T ) ∩ V (D) = ∅,
por lo tanto, tenemos que:
0 = |Hojas(T ) ∩ V (D)| ≥ (k − 2)|U∗ ∩ V (D)| = 0.
Si D cumple con (g), entonces existe un vértice z ∈ V (D) ∩ U∗, por lo que tenemos
que V (D) ∩ U∗ 6= ∅. Por la observación (I) tenemos que:
|Hojas(T ) ∩ V (D)| = |Hojas(T ) ∩ Hojas(D)|.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 101
Además sabemos que:
Si s−
D en Hojas(D), entonces δT (s−
D) = 2, por lo que s−
D /∈ Hojas(T ).
Tenemos dos casos; rD en Hojas(D) o rD /∈ Hojas(D).
Si rD en Hojas(D), entonces δT (rD) = 2; por lo tanto, rD /∈ Hojas(T ).
Por la observación (I) y (II) tenemos que:
|Hojas(T ) ∩ Hojas(D)| = |Hojas(D)| − 2 ≥
∑
v∈V (D)∩U∗
máx{δD(v) − 2, 0} + 2,
por lo que |Hojas(T ) ∩ V (D)| ≥
∑
v∈V (D)∩U∗(δT (v) − 2) = (k − 2)|U∗ ∩ V (D)|.
Si rD /∈ Hojas(D), entonces δT (rD) ≥ 3, por lo tanto, rD /∈ Hojas(T ).
Por la observación (b) tenemos lo siguiente:
|Hojas(T ) ∩ V (D)| = |Hojas(D)| − 1 =
∑
v∈V (D)∩U∗
máx{δD(v) − 2, 0} + 1
≥
∑
v∈V (D)∩U∗
máx{δT (v) − 2, 0} + 1 − 10 ≥
∑
v∈V (D)∩U∗
(δT (v) − 2) = (k − 2)|U∗ ∩ V (D)|.
(ii) Sea D ∈ D2 − D
P
2 .
Si D es una trayectoria con rD = s−
D y como para todo v ∈ U∗ se cumple que δT (v) ≥ 3,
entonces U∗ ∩ V (D) = ∅ ó |U∗ ∩ V (D)| = {rD}.
Si U∗ ∩ V (D) = ∅, entonces tenemos lo siguiente:
|Hojas(T ) ∩ V (D)| ≥ (k − 2)|U∗ ∩ V (D)| + 1.
Si U∗ ∩ V (D) = {rD}, entonces debemos considerar la gráfica
T ′ = T + Qr−
D
+ QsD
+ Rz − r−
DrD − sDs−
D, la cual por el Teorema 1.9.5 es un ár-
bol, como se muestra en la Figura 3.28. Además como r−
D en Qr−
D
, sD en QsD
y z = rD
en Rz tenemos que δT ′(r−
D) = δT (r−
D) + 1 − 1 y δT ′(sD) = δT (sD) + 1 − 1 por lo que T ′
es un k-árbol tal que Domim(T ) ∪ {w} ⊆ Domim(T ′), lo que es una contradicción (a).
Por lo tanto, el caso para U∗ ∩ V (D) = {rD} no es posible.
Figura 3.28: T ′ = T + Qr−
D
+ QsD
+ Rz − r−
DrD − sDs−
D
102 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Si D no es trayectoria, entonces existe un vértice z en P [rD, sD) tal que δT (z) ≥ 3.
Entonces, todo vértice de P (z, sD) tiene grado igual a 2 en T . Si z ∈ U∗, entonces D
satisface la condición (g), por lo que se cumple que D ∈ D
P
2 , lo que contradice el hecho
de que D ∈ D2 − D
P
2 . Por lo tanto, z /∈ U∗.
Por la Afirmación 3.2.9 sabemos que para todo vértice u en U∗ se cumple que
δT (u) = k y además por la observación (I) y (II) obtenemos lo siguiente:
|Hojas(D)| =
∑
v∈V (D)
máx{δD(v) − 2, 0} + 2
≥
∑
v∈V (D)
máx{δT (v) − 2, 0} = |Hojas(T ) ∩ V (D)|
≥
∑
v∈V (D)∩U∗
máx{δT (v) − 2, 0} + δT (z) − 2 ≥ (k − 2)|U∗ ∩ V (D)| + 1.
(iii) Para demostrar este inciso construyamos un nuevo árbol TD≥3
a partir del árbol
T como a continuación sigue: Reemplacemos cada una de las componentes D de D2 por
una arista que une a su respectivo r−
D con sD. Contraemos cada una de las componentes
de D≥3 en un vértice, siguiendo la misma construcción realizada en la Afirmación 3.2.11.
Entonces el número de hojas de T contenidas en
⋃
D∈D1
D es igual al número de hojas
de TD3
; es decir, |Hojas(T ) ∩
⋃
D∈D1
D)| = |Hojas(TD≥3
)|. Como todo vértice D ∈ D≥3
tiene grado igual a |ϑT (D)| en TD3
, por el Lema 1.5 y la observación (I) tenemos que:
|Hojas(T ) ∩
⋃
D1∈D1
V (D)| = |Hojas(TD3
)| =
∑
v∈TD≥3
máx{δD(v) − 2, 0} + 2.
Para todo v ∈ V ∗ ∪ U∗ ∪
⋃
D≥3
V (D) tenemos que δTD≥3
(v) ≥ 3, por lo que:
∑
v∈TD≥3
máx{δD(v) − 2, 0} + 2 ≥
∑
v∈V ∗
(δT (v) − 2) +
∑
v∈U∗∩
⋃
D∈D1
(δT (v) − 2) +
∑
D∈D≥3
(|ϑT (D)| − 2) + 2
≥ (k − 2)|V ∗| + (k − 2)|U∗ ∩
⋃
D∈D1
V (D)| +
∑
D∈D≥3
(|ϑT (D)| − 2) + 2.
(iv) Sea D ∈ D≥3. Consideremos a D′ = T [V (D) ∪ ϑT (D)], entonces el número
de hojas de T contenidas en D es igual al número de hojas contenidas en D′ menos
|ϑT (D)|; es decir,
|Hojas(T ) ∩ V (D)| = |Hojas(D′ \ ϑT (D))|.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 103
Por lo tanto, del Lema 1.5 y de lo anterior se cumple lo siguiente:
|Hojas(D′)| =
∑
v∈V (D′)
máx{δD′(v) − 2, 0} + 2 − |ϑT (D)|
≥
∑
v∈V (D)
máx{δD(v) − 2, 0} + 2 − |ϑT (D)| + 2
≥
∑
v∈V (D)∩U∗
(δT (v) − 2) − |ϑT (D)| + 2 = (k − 2)|U∗ ∩ V (D)| − |ϑT (D)| + 2. ♦
Afirmación 3.2.18. |Hojas(T )| ≥ |D| − |DP
2 |.
Demostración. Por la Afirmación 3.2.17 incisos (i) y (ii) sabemos que:
|
⋃
D∈D2
(Hojas(T ) ∩ V (D))| ≥ (k − 2)|U∗ ∩
⋃
D∈D2
V (D)| + |D2| − |Dp
2|.
Por la Afirmación 3.2.17 inciso (iii) sabemos que:
|
⋃
D∈D1
(Hojas(T ) ∩ V (D))| ≥ (k − 2)|U∗ ∩
⋃
D∈D1
V (D)| −
∑
D∈D≥3
(|ϑT (D)| − 2) + 2.
Por la Afirmación 3.2.17 inciso (iv) sabemos que:
|
⋃
D∈D≥3
(Hojas(T ) ∩ V (D))| ≥ (k − 2)|U∗ ∩
⋃
D∈D≥3
V (D)| −
∑
D∈D≥3
|ϑT (D)| + 2|D≥3|.
Sabemos que:
|Hojas(T )| ≥ |
⋃
D∈D1
(Hojas(T ) ∩ V (D))| + |
⋃
D∈D2
(Hojas(T ) ∩ V (D))|+
+|
⋃
D∈D≥3
(Hojas(T ) ∩ V (D))|.
Sustituyendo se obtiene lo siguiente:
|Hojas(T )| ≥ (k−2)|U∗∩
⋃
D∈D2
V (D)|+|D2|−|DP
2 |+(k−2)|U∗∩
⋃
D∈D1
V (D)|+(k−2)|V ∗|+
+
∑
D∈D≥3
(ϑT (D) − 2) + 2 + (k − 2)|U∗ ∩
⋃
D∈D≥3
V (D)| −
∑
D∈D≥3
|ϑT (D)| + 2|D≥3|. (3.1)
Sabemos que:
(k − 2)|U∗ ∩
⋃
D∈D2
V (D)| + (k − 2)|U∗ ∩
⋃
D∈D1
V (D)|+
104 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
+(k − 2)|U∗ ∩
⋃
D∈D≥3
V (D)| + (k − 2)|V ∗| ≥
≥ (k − 2)|U∗ ∪ V ∗|.
Además tenemos que:
∑
D∈D≥3
|ϑT (D)| − 2|D≥3| =
∑
D∈D≥3
(|ϑT (D)| − 2).
Por lo que de la ecuación 3.1 y de lo anterior obtenemos:
|Hojas(T )| ≥ (k − 2)|V ∗ ∪ U∗| + |D2| − |DP
2 | + 2. (3.2)
Por la Afirmación 3.2.11 sabemos que:
(k − 2)|V ∗ ∪ U∗| ≥ (k − 2)|V ∗| + (k − 2)
∑
D∈D≥3
(|ϑT (D)| − 1).
Por lo que de la ecuación 3.2 obtenemos lo siguiente:
|Hojas(T )| ≥ (k − 2)|V ∗| + (k − 2)
∑
D∈D≥3
(ϑT (D) − 1) + |D2| − |DP
2 | + 2. (3.3)
Como
∑
D∈D≥3
(|ϑT (D)|−1−1)+ |D≥3| =
∑
D∈D≥3
(|ϑT (D)|−1), entonces al sustituir
|V ∗| = n y lo anterior en la ecuación 3.3 tenemos lo siguiente:
|Hojas(T )| ≥ (k − 2)n +
∑
D∈D≥3
(|ϑT (D)| − 2) + |D≥3| + |D2| − |DP
2 | + 2. (3.4)
De la Afirmación 3.2.2 parte (ii) sabemos que:
|D1| = (k − 2)n +
∑
D∈D≥3
(|ϑT (D)| − 2) + 2,
por lo que de la ecuación 3.4 tenemos lo siguiente:
|Hojas(T )| ≥ |D1| + |D≥3| + |D2| − |DP
2 |. (3.5)
Además sabemos que |D| ≥ |D1| + |D≥3| + |D2|.
Por lo tanto, de la ecuación 3.5 obtenemos que |Hojas(T ) ≥ |D| − |DP
2 |. ♦
De la afirmación 3.2.16 tenemos lo siguiente α2(m+1)(G) ≥ |YHojas ∪ YT ray ∪ {w}|.
Por la Afirmación 3.2.14 sabemos que YHojas ∩ YT ray = ∅
|YHojas ∪ YT ray ∪ {w}| = |YHojas| + |YT ray| + 1.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 105
Por la Afirmación 3.2.4 sabemos que para dos vértices x1 y x2 distintos en Hojas(T )
tenemos que yx1
6= yx2
en YHojas, por lo que tenemos que |YHojas| = |Hojas(T )|.
Nuevamente por la Afirmación 3.2.14 sabemos que para D1 6= D2 en D
p
2 tenemos dos
vértices yD1
y yD2
distintos en YT ray, por lo que |YT ray| = |Dp
2|. Por lo que, tenemos que
|YHojas| + |YT ray| + 1 = |Hojas(T )| + |DP
2 | + 1.
Por la Afirmación 3.2.18 sabemos que
|Hojas(T )| ≥ |D| − |Dp
2|,
así tenemos que
|Hojas(T )| + |DP
2 | + 1 ≥ |D| − |Dp
2| + |Dp
2| + 1 = |D| + 1.
De la Afirmación 3.2.2 sabemos que: |D| + 1 = (k − 1)n + 2.
Por lo tanto, α2(m+1)(G) ≥ (k − 1)n + 2.
Por hipótesis del Teorema 3.2.1 tenemos que α2(m+1)(G) ≤ (k − 1)n + 1.
Por lo que (k − 1)n + 1 ≥ α2(m+1)(G) ≥ (k − 1)n + 2,
(k − 1)n + 1 ≥ (k − 1)n + 2.
Esto es una contradicción.
Por lo tanto, G tiene un k-árbol que m-domina a G.
Probaremos que efectivamente las condiciones del Teorema 3.2.1 son justas
en el entendido de que existe una familia de gráficas G que satisface la
condición α2(m+1)(G) = (k − 1)n + 2, pero no tiene un k-árbol que m-domina a
G.
Para esto construiremos una gráfica G como sigue a continuación:
Sean k ≥ 2, m ≥ 1 y n ≥ 1 tres enteros positivos, tomemos a Di,1, Di,2, . . . , Di,m
como las copias de gráficas completas de orden n, donde 1 ≤ i ≤ (k − 1)n + 2,
tal que para cada 1 ≤ i ≤ (k − 1)n + 2 y 1 ≤ j ≤ m − 1 unimos todos los
vértices de Di,j con todos los vértices de Di,j+1; es decir, Di,j + Di,j+1. Para
cada 1 ≤ i ≤ (k − 1)n + 2, agregamos vi un nuevo vértice y lo unimos a todos
los vértices de Di,m. Añadimos H una gráfica de orden n, tal que para cada
1 ≤ i ≤ (k − 1)n + 2 hacemos adyacente a cada vértice de H con cada vértice
de Di,1. Con esto obtenemos G la gráfica deseada como se muestra en la
siguiente Figura.
106 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Figura 3.29: Construcción de G
Ahora notemos que G es una gráfica n-conexa. Demostraremos que para
todo par de vértices en G existen al menos n trayectorias internamente
ajenas entre dicho par de vértices.
Sean x1 y x2 dos vértices de G. Consideremos los siguientes casos:
Caso 1) Si {x1, x2} ⊆ H o {x1, x2} ⊆ Di,j para i en {1, 2, ..., (k − 1)n + 2} y j en
{2, ..., m}.
Caso 1.1) Si {x1, x2} ⊆ H, entonces podemos construir las n trayectorias
internamente ajenas entre x1 y x2 pasando por D1,1 como a continuación se
muestra: como |D1,1| = n tomemos a zl en D1,1 y construimos la trayectoria
Tl = (x1, zl, x2) para l en {1, 2, ..., n}.
Caso 1.2) Si {x1, x2} ⊆ Di,j para j en {2, 3, ..., n}, entonces como todos los
vértices de Di,j son adyacentes a los vértices de Di,j−1 y |Di,j−1| = n, tomemos
a wl en Di,j−1 para l en {1, 2, ..., n} y construimos las n (x1, x2)-trayectorias
internamente ajenas de la forma siguiente: Tl = (x1, wl, x2). Para j = 1 sabemos
por la construcción de G que todos los vértices de H son adyacentes a todos
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 107
los vértices de la componente Di,1 y tenemos que |Di,1| = n, entonces tomemos
a hl en V (H) con l en {1, 2, ..., n} y construimos las n (x1, x2)-trayectorias
internamente ajenas de la siguiente forma: Tl = (x1, hl, x2).
Caso 2) Si x1 está en Di,j y x2 está en Di,l para i y l en {1, 2, ..., (k − 1)n + 2},
con i fijo y l 6= i, entonces consideremos los siguientes subcasos:
Caso 2.1) Si x1 ∈ V (Di,j) y x2 ∈ V (Di,j−1) para i en {1, 2, ..., (k − 1)n + 2} y j
en {2, 3, ..., m}, entonces como x1 es adyacente a cada uno de los n vértices
de Di,j−1 y como Di,j−1 es completa tenemos que x2 es adyacente a todos los
vértices en V (Di,j−1) \ {x2}, por lo que tenemos n (x1, x2)-trayectorias inter-
namente ajenas.
Caso 2.2) Si x1 ∈ V (Di,j) y x2 ∈ V (Di,m′) para i en {1, 2, ..., (k − 1)n + 2} y {m′, j}
en {1, 2, ..., m}, con j 6= m′, j − 1 6= m′ y j > m′, entonces tomemos a u
(i,ρ)
l en
V (Di,ρ) para toda m′ < ρ < j con l en {1, 2, ..., n}, como u
(i,ρ)
l es adyacente a
u
(i,ρ−1)
l con u
(i,ρ−1)
l ∈ V (Di,ρ−1), podemos construir n (x1, x2)-trayectorias inter-
namente ajenas como sigue (x1, u
(i,j−1)
l , u
(i,j−2)
l , ..., u
(i,m′+1)
l , x2), para toda para
i ∈ {1, 2, ..., (k − 1)n + 2}, j ∈ {1, 2, ..., m}, m′ < ρ < j y l ∈ {1, 2, ..., n}.
108 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Caso 3) Si x1 ∈ V (Di,j) y x2 ∈ V (Dk′,m′) para {i, k′} ⊆ {1, 2, ..., (k − 1)n + 2} y
{m′, j} ⊆ {1, 2, ..., m}, con i 6= k′ y j 6= m′, entonces por el caso (2) encon-
tramos al menos n (x1, ui,1
l )-trayectorias, por otro lado tenemos n (x2, uk′,1
l )-
trayectorias para l en {1, 2, ..., n}. Como los vértices de H son adyacentes
a todos los vértices de Di,1 y Dk′,1 tomemos a hl un vértice en H con l en
{1, 2, ..., n}, que es adyacente a u
(i,1)
l y a u
(k′,1)
l . Por lo tanto, tenemos n (x1, x2)-
trayectorias internamente ajenas en G obtenidas de la siguiente manera:
(x1, u
(i,j−1)
l , u
(i,j−2)
l , ..., u
(i,1)
l , hl) ∪ (hl, u
(k′,1)
l , ..., x2),
para toda para l en {1, 2, ..., n}, {i, k′} en {1, 2, ..., (k−1)n+2} y {m′, j} en {1, 2, ..., m},
con i 6= k′ y j 6= m′.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 109
Caso 4) x1 = vi y x2 ∈ V (Di,j) con i en {1, 2, ..., (k − 1)n + 2} y j en {1, 2, ..., m}.
Caso 4.1) Si x1 = vi y x2 ∈ V (Di,j) para j = m, entonces como el vértice vi es
de grado n podemos construir como en el caso (2.1) las n (vi, x2)-trayectorias
internamente ajenas.
Caso 4.2) Si x1 = vi y x2 ∈ V (Di,j) con i en {1, 2, ..., (k−1)n+2} y j en {1, 2, ..., m−
1}, entonces como el vértice vi es de grado n podemos construir como en el
caso (2.2) las n (vi, x2)-trayectorias internamente ajenas.
110 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Caso 5) Si x1 = vi y x2 = hl en V (H) con i en {1, 2, ..., (k − 1)n + 2} y l en
{1, 2, ..., n}, entonces como el vértice vi es de grado n podemos construir
como en el caso (3) las n (vi, hl)-trayectorias internamente ajenas.
Caso 6) Si x1 = vi y x2 ∈ V (Dk,m′) para {i, k} en {1, 2, ..., (k − 1)n + 2} y {m′, j} ⊆
{1, 2, ..., m}, con i 6= k′ y j 6= m′, entonces como el vértice vi es de grado
n podemos construir como en los casos (3) y (5) las n (vi, x2)-trayectorias
internamente ajenas pasando por H.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 111
Caso 7) Si x1 = vi y x2 = vk para {i, k} ⊆ {1, 2, ..., (k − 1)n + 2} con i 6= k′,
entonces como el vértice vi es de grado n podemos construir como en los
casos (3) y (5) las n (vi, vk)-trayectorias internamente ajenas pasando por H.
Por los casos anteriores concluimos que G es n-conexa.
Lema 3.3. La gráfica bipartita Kn,(k−1)n+2 no tiene un k-árbol generador.
Demostración. Supongamos por contradicción que Kn,(k−1)n+2 tiene un k-árbol genera-
dor T . Como T es árbol se cumple que |A(T )| = p − 1 y como p = (k − 1)n + 2 + n,
entonces |A(T )| = (k − 1)n + 2 + n − 1 = (k)n + 1.
Ya que Kn,(k−1)n+2 es una gráfica bipartita, tenemos una partición P = (V1, V2) de
V (Kn,(k−1)n+2) tal que |V1| = n y |V2| = (k−1)n+2. Como T es k-árbol generador tene-
mos que V1 ⊆ V (T ), por lo que se tiene que δT [V1](x) ≤ k para todo x en T [V1], entonces
|A(T )| ≤ (k)n. Por lo tanto, |A(T )| = (k)n + 1 ≤ (k)n lo cual es una contradicción.
Por lo tanto, Kn,(k−1)n+2 no tiene un k-árbol generador.
Veamos que G no tiene un k-árbol m-dominante. Supongamos por contra-
dicción que G tiene un k-árbol m-dominante T . Para que T sea m-dominante
se debe cumplir que existe un xj en D1,j para toda j en {1, 2, ..., (k − 1)n + 1}
que esta en V (T ), supongamos por contradicción que no existe un vértice xj
en D1,j que este en V (T ), entonces dG(vj, T ) > m lo que contradice que T m-
domine a G ó T es inconexa. Como no existen aristas entre Dj,1 y Dj−1,1 para
toda j en {2, 3, ..., (k − 1)n + 1}, entonces es necesario para que T sea conexa
tener al menos una arista de cada D1,j a H para toda j en {1, 2, ..., (k−1)n+1}.
Como el número de vértices de H es igual a n y por lo visto anteriormen-
te son necesarias al menos (k − 1)n + 1 aristas entre H y las Dj,1 para j en
{2, 3, ..., (k − 1)n + 1}, tenemos como subgráfica de G a la gráfica bipartita
112 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Kn,(k−1)n+2, la cual por el lema anterior no tiene un k-árbol generador. Por
lo tanto, G no tiene un k-árbol m-dominante.
Por otro lado, recordemos que:
αl(G) = máx{|S| : S ⊆ V (G) dG(x, y) ≥ l con x 6= y y {x, y} ⊆ S}.
Afirmamos que: α2(m+1)(G) = máx|{vi : 1 ≤ i ≤ (k − 1)n + 2}| = (k − 1)n + 2.
Recordemos que los vértices vi en V (G), son los vértices adyacentes a los
vértices de la componente Di,m, con i en {1 ≤ i ≤ (k − 1)n + 2}. Sea S =
{vi : 1 ≤ i ≤ (k − 1)n + 2}. Para los vértices vi en S, como se tiene que
dG(vi, H) = m + 1 para cada uno de ellos, entonces si tomamos dos a dos
estos vértices resulta que se tiene dG(vi, vi−1) ≥ 2(m + 1) y además tenemos
exactamente (k − 1)n + 2 vértices vi. Ahora como cada una de las Di,j son
completas, entonces tenemos que: α2(m+1)(G) = |S|.
Con esto se prueba que efectivamente las condiciones del Teorema 3.2.1 son
justas.
A partir de la demostración del Teorema 3.2.1 se puede deducir un algoritmo
a seguir para obtener un k-árbol m dominante en una gráfica n-conexa que
cumple con las hipótesis del Teorema 3.2.1.
A continuacion presentamos dicho algoritmo:
Paso 1) Sea G una gráfica n-conexa que cumple que α2(m+1)(G) ≤ (k − 1)n + 1. Tomar
un árbol T tal que T ≤ G y |V (T )| = n.
Paso 2) Si T m-domina a G, entonces el proceso finaliza. Si T no m-domina a G,
entonces existe un vértice w en V (G) − Domim(T ). Tomar las Q1, Q2, ..., Qn
(w, T )-trayectorias internamente ajenas tales que para toda i en {1, 2, ...n}
{vi} = V (Qi) ∩ V (T ) y {v1, v2, ..., vn} = V ∗ (conjuntos definidos en la demos-
tración del Teorema 3.2.1). Ir al paso siguiente.
Paso 3) Si δT (vi) ≤ k − 1 para algún vi en V ∗, entonces considerar el siguiente árbol:
T ′ ∼ T + Qi
e ir al paso 2 (Afirmación 3.2.1). Si esto no se cumple, entonces para todo
vértice vi en V ∗ δT (vi) = k con i en {1, 2, ..., n}. Ir al paso siguiente.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 113
Paso 4) Si existe una arista vivj en A(T ) con vi 6= vj, entonces considerar el árbol:
T ′ ∼ T + Qvi
+ Qvj
− vivj
e ir al paso 2 (Afirmación 3.2.2). Si esto no se cumple, entonces para todo
{i, j} ⊆ {1, 2, ..., n} con i 6= j vivj /∈ A(T ). Ir al paso siguiente.
Paso 5) Si para un vértice x en Hojas(T ) se cumple que Domim(T ) = Domim(T − x)
y x es adyacente a algún vi en V (T ), entonces considerar el árbol siguiente:
T ′ ∼ T − x + Qvi
e ir al paso 2 (Afirmación 3.2.3). Si esto no se cumple, entonces para todo
vértice x en Hojas(T ) x no es adyacente a algún vértice vi con i en {1, 2, ..., n}
ó Domim(T ) ⊇ Domim(T − x). Ir al siguiente paso.
Paso 6) Si x ∈ Hojas(T ), yx en Domim(T ) − V (T ) con dG(yx, w) ≤ m y P es una
(x, w)-trayectoria ó una (x, yx)-trayectoria con V (P ) \ {x} ⊆ V (G) − V (T ),
entonces considerar el árbol:
T ′ ∼ T + P
e ir al paso 2 (Afirmación 3.2.5). Si esto no se cumple, entonces para todo vértice
x en Hojas(T ), yx en Domim(T ) − V (T ) se cumple que dG(yx, w) > m ó no
existe P una (x, w)-trayectoria ó una (x, yx)-trayectoria con vértices interiores
contenidos en G − T . Ir al paso siguiente.
Paso 7) Si x ∈ Hojas(T ) y Domim(T − x) = Domim(T ), entonces considerar el árbol
siguiente:
T ′ ∼ T − x
e ir al paso 2 (por la Afirmación 3.2.3). Si esto no se cumple, entonces tomar
a YHojas = {yx : x ∈ Hojas(T )} y S(y) = {x ∈ Hojas(T ) : yx = y}. Ir al
paso siguiente.
Paso 8) Si para {x1, x2} ⊆ Hojas(T ) existe P una (x1, x2)-trayectoria con vértices
interiores en G − T , P ′ la (x1, x2)-trayectoria en T y e ∈ A(P ′) tal que e incide
en un vértice va en V ∗ para alguna a en {1, 2, ..., n}, entonces considerar el
árbol siguiente:
T ′ ∼ T + P + Qa − e
e ir al paso 2 (por la Afirmación 3.2.6). Si esto no se cumple, entonces P ′∩V ∗ =
∅. Ir al paso siguiente.
Paso 9) Si para {x1, x2} ⊆ Hojas(T ) existe P una (x1, x2)-trayectoria con vértices
interiores en G − T , P ′ la (x1, x2)-trayectoria en T , P ′ ∩ V ∗ = ∅ y e ∈ A(P ′)
114 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
una arista que incide en un vértice en P ′ de grado mayor o igual que 3, entonces
considerar el árbol siguiente:
T ′ ∼ T + P − e
e ir al paso 2 (por la Afirmación 3.2.6). Si esto no se cumple, entonces tomar
a: D1 = {D ∈ D : |ϑT (D)| = 1}, D2 = {D ∈ D : |ϑT (D)| = 2} y
D≥3 = {D ∈ D : |ϑT (D)| ≥ 3} los conjuntos de componentes conexas de
T −V ∗ donde ϑT (D) es el conjunto de vecinos de D en T (conjuntos definidos en
la demostración del Teorema 3.2.1). Tomar a D1 una componente de T −V ∗ tal
que ϑT (D1) = {v1} y ∆T ([D1]) ≤ k−1. Tomar a R1, R2, ..., Rn las (D1, T −D1)-
trayectorias con vértices interiores en G − T y vértices finales {u1, u2, ..., un} =
U∗ (dos conjuntos definidos en la demostración del Teorema 3.2.1). Ir al paso
siguiente.
Paso 10) Si existe P una (w, D1)-trayectoria, entonces considerar al árbol:
T ′ ∼ T + P
e ir al paso 2 (Afirmación 3.2.8). Si esto no se cumple, entonces no existe
una (w, D1)-trayectoria. Tomar a rD el vértice raíz de la componente D, r−
D el
vértice antecesor en T del vértice rD, s−
D el vértice final de la componente D,
sD el vértice sucesor en T del vértice s−
D y Q1 la (v1, w)-trayectoria. Ir al paso
siguiente.
Paso 11) Si δT (u) < k, para algún vértice u ∈ U∗ y Ra es una (D1, T − D1)-trayectoria,
entonces considerar el siguiente árbol:
T ′ ∼ (T + Ra + Q1) − rD1
r−
D1
e ir al paso 2 (Afirmación 3.2.9). Si esto no se cumple, entonces δT (u) = k para
todo vértice u ∈ U∗. Ir al paso siguiente.
Paso 12) Si para D ∈ D≥3 existe un vértice u ∈ U∗ ∩ ϑT (D − r−
D), entonces considerar
el árbol siguiente:
T ′ ∼ T + Ra − uu−
e ir al paso 2 (por Afirmación 3.2.10). Si esto no se cumple, entonces |D1 ∪D≥3|
es mínimo y tomar a D ∈ D
p
2 una componente pseudotrayectoria (conjunto
definido como en el Teorema 3.2.1). Ir al paso siguiente.
Paso 13) Si D ∈ D
p
2, entonces considerar los siguientes casos:
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 115
13.1) Si D ∈ D
p
2 cumple que rD = s−
D y D = {rD} (de acuerdo con la pro-
piedad (e) de la demostración del Teorema 3.2.1), entonces considerar el
siguiente árbol:
T ′ ∼ T + Qr−
D
+ QsD
− rD
e ir al paso 2 (Afirmación 3.2.12).
13.2) Si D ∈ D
p
2 cumple que D es una trayectoria con rD 6= s−
D (de acuerdo
con la propiedad (f) de la demostración del Teorema 3.2.1), entonces
considerar el árbol siguiente:
T ′ ∼ T + Qr−
D
+ QsD
− P [rD, s−
D]
e ir al paso 2 (Afirmación 3.2.12).
13.3) Si D ∈ D
p
2 cumple que existe un vértice zD en P (rD, s−
D], tal que para
todo vértice z ∈ P (zD, s−
D] se tiene que δT (z) = 2 (de acuerdo con la
propiedad (g) de la demostración del Teorema 3.2.1), entonces considerar
el siguiente árbol:
T ′ ∼ T + Qr−
D
+ QsD
+ RzD
− rD, r−
D − sDs−
D
e ir al paso 2 (Afirmación 3.2.12).
Si esto no se cumple, entonces tomar a W = {y ∈ V (G) : dG(y, P [xD, s−
D]) =
m}. Ir al paso siguiente.
Paso 14) Si
W = ∅ ó dG(y, T − P [xD, s−
D]) ≤ m
para toda y ∈ W , entonces considerar los siguientes casos:
14.1) Si D ∈ D
p
2 cumple que rD = s−
D y D = {rD} (de acuerdo con la pro-
piedad (e) de la demostración del Teorema 3.2.1), entonces considerar el
siguiente árbol:
T ′ ∼ T + Qr−
D
+ QsD
− D
e ir al paso 2 (Afirmación 3.2.13).
14.2) Si D ∈ D
p
2 cumple que D es una trayectoria con rD 6= s−
D (de acuerdo
con la propiedad (f) de la demostración del Teorema 3.2.1), entonces
considerar el siguiente árbol:
T ′ ∼ T + Qr−
D
+ QsD
− P [rD, s−
D],
e ir al paso 2 (Afirmación 3.2.13).
116 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
14.3) Si D ∈ D
p
2 cumple que existe un vértice zD en P (rD, s−
D], tal que para
todo vértice z ∈ P (zD, s−
D] se tiene que δT (z) = 2 (de acuerdo con la
propiedad (g) de la demostración del Teorema 3.2.1), entonces considerar
el siguiente árbol:
T ′ ∼ T + Qr−
D
+ QsD
+ RzD
− P (zD, sD) − rDr−
D,
e ir al paso 2 (Afirmación 3.2.13).
Si esto no se cumple, entonces tomar a Q una (w, S(y))-trayectoria con vértices
interiores en G − T , donde S(y) = V (P [xD, s−
D]). Ir al paso siguiente.
Paso 15) Si D ∈ D
p
2 y existe Q una (w, S(y))-trayectoria con vértices interiores en G−T
para S(y) ⊆ D, entonces considerar los siguientes casos:
15.1) Si D ∈ D
p
2 cumple que rD = s−
D y D = {rD} (de acuerdo con la propiedad
(e) de la demostración del Teorema 3.2.1), entonces considerar el árbol:
T ′ ∼ T + Q
e ir al paso 2 (Afirmación 3.2.15).
15.2) Si D ∈ D
p
2 cumple que D es una trayectoria con rD 6= s−
D (de acuerdo
con la propiedad (f) de la demostración del Teorema 3.2.1), entonces
considerar el árbol:
T ′ ∼ T + Q
e ir al paso 2 (Afirmación 3.2.15).
15.3) Si D ∈ D
p
2 cumple que existe un vértice zD en P (rD, s−
D], tal que para
todo vértice z ∈ P (zD, s−
D] se tiene que δT (z) = 2 (de acuerdo con la
propiedad (g) de la demostración del Teorema 3.2.1), entonces para w0
el primer vértice en QsD
∩ Q considerar el árbol:
T ′ ∼ T + QsD
+ Q[w0, z] − P (z, sD)
e ir al paso 2 (Afirmación 3.2.15).
Si esto no se cumple, entonces existe Q una (D1, S(y))-trayectoria con vértices
interiores en G − T , donde S(y) = V (P [xD, s−
D]). Ir al paso siguiente.
Paso 16) Si D ∈ D
p
2 y existe Q una (D1, S(y))-trayectoria con vértices interiores en
G − T para S(y) ⊆ D, entonces considerar el árbol:
T ′ ∼ T + Qr−
D
+ QsD
+ Q − rDr−
D − s−
DsD
e ir al paso 2 (Afirmación 3.2.15). Si esto no se cumple, entonces ir al paso
siguiente.
3.2. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS 117
Paso 17) Si D ∈ D
p
2, Q una (S(y1), S(y2))-trayectoria con vértices interiores conteni-
dos en G − T , {S(y1), S(y2)} ⊆ D y S(y1) 6= S(y2), entonces considerar los
siguientes casos:
17.1) Si {y1, y2} ⊆ YHojas, entonces se procede como en el paso 8.
17.2) Si y1 en YHojas y y2 en YT ray, entonces considerar los siguientes subcasos:
17.2.a) Si S(y1) en Hojas(T )∩D, S(y1) = x y D cumple que existe un vértice
zD en P (rD, s−
D], tal que para todo vértice z ∈ P (zD, s−
D] se tiene que
δT (z) = 2 (de acuerdo con la propiedad (g) de la demostración del
Teorema 3.2.1), entonces considerar el árbol:
T ′ ∼ (T + Qr−
D
+ QsD
+ RzD
+ Q) − P (zD, sD) − r−
DrD − zDz∗,
donde z∗ en P (zD, x). Ir al paso 2 (Afirmación 3.2.16).
17.2.b) Si S(y2) en Hojas(T ) y además S(y2) /∈ V (D), entonces considerar el
árbol:
T ′ ∼ (T + Qr−
D
+ QsD
+ Q) − P (zD, sD) − r−
DrD
e ir al paso 2 (Afirmación 3.2.16).
17.3) Si {y1, y2} ⊆ YT ray, entonces considerar lo siguiente:
17.3.a) Si Da en D
p
2 y además cumple que rD = s−
D y D = {rD} ó cumple
que D es una trayectoria con rD 6= s−
D (de acuerdo con las propiedades
(e) ó (f) de la demostración del Teorema 3.2.1), entonces considerar el
árbol:
T ′ ∼ (T + Qr−
Da
+ QsDa
+ QsDb
+ Q) − P (zDb
, sDb
) − r−
Da
rDa
− sDa
s−
Da
e ir al paso 2 (Afirmación 3.2.16).
17.3.b) Si {Da, Db} ⊆ D
p
2 y además existe un vértice zDa
en P (rDa
, s−
Da
], tal que
para todo vértice z ∈ P (zDa
, s−
D−a] se tiene que δT (z) = 2 y existe un
vértice zDb
en P (rDb
, s−
Db
], tal que para todo vértice z ∈ P (zDb
, s−
D−b] se
tiene que δT (z) = 2 (de acuerdo con la propiedad (g) de la demostración
del Teorema 3.2.1) cumplen con la propiedad (g), entonces considerar
el árbol T ′ siguiente:
(T + Qr−
Da
+ QsDa
+ QsDb
+ Q) − P (zDa
, sDa
) − P (zDb
, sDb
) − r−
Da
rDa
e ir al paso 2 (Afirmación 3.2.16).
118 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Si esto no se cumple, entonces tomar a D ∈ D2 − D
p
2 una componente conexa
de T − V ∗; que es una trayectoria con rD = s−
D. Ir al paso siguiente.
Paso 18) Si D ∈ D2 − D
p
2 es una trayectoria con rD = s−
D, D contiene una hoja de T y
U∗ ∩ D = {rD}, entonces consideramos a:
T ′ ∼ (T + Qr−
D
+ QsD
+ RrD
) − r−
DrD − s−
DsD.
e ir al paso 2 (Afirmación 3.2.17).
Con este último paso del algoritmo cubrimos todas las posibilidades para
encontrar un k-árbol m-dominante en una gráfica G n-conexa que cumpla
las hipótesis del Teorema 3.2.1.
3.3. Aplicación sobre una red de distribución de
agua potable
En esta sección implementaremos el algoritmo a una gráfica. La cual la
obtendremos a partir de un problema en una red de distribución de agua
potable.
Deseamos mejorar la distribución de agua potable en el cuadro central del
centro histórico de la ciudad de Oaxaca de Juárez (Figura 3.30). Para lograr
esto se desea que en todos los puntos de la red el agua llegue con una presión
mínima establecida. Con este objetivo se busca implementar la infraestruc-
tura necesaria sobre un ramal principal, en el cual se tenga alta presión y
estaciones de rebombeo para satisfacer la demanda de una presión mínima
en todos los puntos de la red. En nuestro cuadro la topografía es plana.
Figura 3.30: Red de distribución de agua potable.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE119
Dicho cuadro de la ciudad tiene conFiguración de una reja, entonces puede
ser modelado por una gráfica G, donde los vértices representan las intersec-
ciones de las cuadras y las aristas las tuberías a lo largo de las calles, como
se muestra en la Figura 3.31.
Figura 3.31: Gráfica obtenida a partir de la red de distribución de agua potable.
Para garantizar que el servicio llegue con una presión mínima deseada es
necesario entender lo siguiente:
Para mantener una presión mínima en todos los puntos es necesario identificar
los vértices candidatos a ser estaciones de rebombeo, los cuales deberán estar
localizados sobre el ramal de alta presión.
A partir de la salida del agua del ramal de alta presión, la presión comien-
za a disminuir, de acuerdo con el “Manual de Agua Potable, alcantarillado y
saneamiento" sabemos que a distancia 2 del ramal de alta presión se tiene la pre-
sión mínima deseada [8], por lo que los puntos de la red deberan estar a distancia
menor o igual que 2 del ramal de alta presión.
120 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Entonces encontrar el ramal de alta presión se traduce en buscar en G una
subgráfica que sea conexa y sin ciclos, tal que la distancia de los vértices de
G a la subgráfica obtenida sea menor o igual a 2, lo que permite tener una
presión mínima en todos lo vértices de G.
Por lo anterior una posible solución es encontrar un árbol que 2-domine
a la gráfica G. Pues la 2-dominación nos determina la distancia máxima
en la que la presión mínima del agua se tiene, entendiendo que al exceder
dicha distancia se tendrá una presión menor a la presión mínima deseada.
Cualquier vértice del árbol solución será candidato a ser una estación de
rebombeo.
Se puede obtener una solución usando el resultado visto en este capítulo, el
cual nos permite encontrar un k-árbol que 2-domine a G, observemos que
al variar el valor de k es posible encontrar varias soluciones de las cuales
escogeremos la que tenga menos vértices de G.
De acuerdo con el Teorema 3.2.1 sabemos que para que G tenga un k-árbol
2-dominante, G debe cumplir la condición α2(m+2)(G) ≤ (k − 1)n + 1.
Observemos que como G es conexa y no tiene vértices de corte, tenemos que
K(G) ≥ 2, por lo que G es 2-conexa, por lo tanto, n = 2. Como buscamos que
se 2-domine a G tenemos que m = 2. Por último como el grado máximo de
G es igual a 4, entonces podemos encontrar tres posibles soluciones para los
valores k en {2, 3, 4}.
Encontraremos para m = 2 cual es el valor de α2(2+1)(G) = α6(G). Por la
definición del invariante tenemos que:
α2(2+1)(G) = máx{|S| : S ⊆ V (G), dG(x, y) ≥ 2(2 + 1) para {x, y} ⊆ S},
entonces debemos encontrar el subconjunto máximo de vértices S que cum-
pla que todo par de vértices de S estén a distancia mayor o igual que 6.
Sea S ⊆ V (G) tal que S = {x1, x2, x4} como se muestra en la Figura 3.32.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE121
Figura 3.32: S = {x1, x2, x4}.
Afirmamos que entre todo par de vértices de S tenemos que dG(xi, xj) ≥ 6
con i 6= j y {i, j} ⊆ {1, 2, 4}. Podemos observar que:
dG(x1, x2) = 6, dG(x1, x4) = 9 y dG(x2, x4) = 7.
Por lo que, α6(G) ≥ 3.
Supongamos que existe un S ′ ⊆ V (G) tal que |S ′| = α6(G) > 3. Si x1 en S ′,
entonces sea N≤5(x1) la vecindad del vértice x1 que está a distancia menor o
igual que 5 de x1; por lo que los vértices de N≤5(x1) no pueden estar en S ′.
Consideremos a G′ = G\N≤5(x1) como se muestra en la Figura 3.33. Sabemos
que |V (G)| = 42 y |N≤5(x1)| ≤ 21. Entonces:
|V (G′)| ≤ |V (G)| − 21, |V (G′)| ≤ 21.
Figura 3.33: G′ = G \ N≤5(x1).
122 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Tomemos a x2 y x3 dos vértices de G′, los cuales por la conFiguración de G′
son candidatos a estar en S ′. Supongamos sin pérdida de generalidad x2 en
S ′, entonces sea N≤5(x2) la vecindad del vértice x2 que está a distancia menor
o igual que 5 de x2; por lo que los vértices de N≤5(x2) no pueden estar en S ′.
Consideremos la gráfica G′′ = G′ \ N≤5(x2) como se muestra en la Figura 3.34.
Sabemos que |V (G′)| ≤ 21 y |N≤5(x2)| ≤ 15. Entonces |V (G′′)| ≤ |V (G′)| − 15,
|V (G′′)| ≤ 6.
Figura 3.34: G′′ = G′ \ N≤5(x2).
Tomemos a x4 y x5 dos vértices de G′′, los cuales por la conFiguración de G′′
son candidatos a estar en S ′. Supongamos sin pérdida de generalidad que
x4 en S ′, entonces sea N≤5(x4) la vecindad del vértice x4 que está a distancia
menor o igual que 5 de x4; por lo que los vértices de N≤5(x4) no pueden estar
en S ′. Pero como todo vértice de G′′ esta a distancia menor que 5 de x4,
entonces no es posible tomar otro vértice que esté en S ′. Por lo tanto, si x1
en S ′, entonces |S ′| = 3.
Si x1 /∈ S ′, entonces para todo par de vértices {y, z} ⊆ V (G − x1) tenemos que
dG(z, y) ≤ 10, como la distancia máxima en G es 11, entonces con dos vértices
u y v tal que dG−x1
(u, v) ≥ 6 tendríamos que el resto de los vértices de G están
a distancia menor o igual que 5 de u o de v. Por lo tanto, |S ′| = 2.
Por lo tanto, α6(G) = 3.
Ahora podemos proceder con las soluciones donde observaremos que la con-
dición del Teorema 3.2.1 se cumple para los tres valores de k antes de poder
aplicar el algoritmo.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE123
Solución 1.- Veamos la solución para m = 2, n = 2 y k = 2. Como vimos an-
teriormente se tiene lo siguiente para la condición del Teorema 3.2.1
α2(2+1)(G) = α6(G) = 3 ≤ (2 − 1)2 + 1 = 3, por lo tanto, G tiene
un 2-árbol 2-dominante, el cual lo encontraremos mediante el algoritmo.
Paso 1) Tomamos a T un árbol de orden 2 en G como se muestra en la
Figura 3.35.
Figura 3.35: T de orden 2.
Paso 2) Como T no 2-domina a G, entonces existe un vértice w en
V (G)−Domi2(T ) y consideremos a V ∗ = {v1, v2} tal que V ∗ ⊂ V (T )
como se muestra en la Figura 3.36.
Figura 3.36: T de orden 2.
124 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Paso 3) Como δT (v1) = δT (v2) = 1, entonces tomemos a Q2 la
(v2, w)-trayectoria y consideremos a T1 ∼ T + Q2, como se muestra
en la Figura 3.37, el cual es un 2-árbol pues se tiene que ∆G(T1) = 2.
Figura 3.37: T1 ∼ T + Q2.
Paso 2) Como T1 no 2-domina a G, entonces existe un vértice w1 en
V (G) − Domi2(T1) y consideramos a V ∗
1 = {v1
1, v1
2} tal que
V ∗
1 ⊂ V (T1) como se muestra en la Figura 3.38.
Figura 3.38: T1.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE125
Paso 3) Como δT1
(v1
1) = δT1
(v1
2) = 2, entonces pasamos al paso siguiente.
Paso 4) Como v1
1v1
2 /∈ A(T1), entonces debemos pasar al paso siguiente.
Paso 5) Como v1
2 es adyacente a una hoja de T1, podemos considerar el
siguiente 2-árbol T2 ∼ T1 − x + Q2, como se muestra en la Figura
3.39, donde Q2 es una (v1
2, w1)-trayectoria.
Figura 3.39: T2 ∼ T1 − x + Q2.
Paso 2) Como T2 no 2-domina a G, entonces existe un vértice w2 en
V (G) − Domi2(T2) y consideremos a V ∗
2 = {v2
1, v2
2} tal que
V ∗
2 ⊂ V (T2) como se muestra en la Figura 3.40.
Figura 3.40: T2.
126 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Paso 3) Como δT2
(v2
1) = δT2
(v2
2) = 2, entonces pasamos al paso siguiente.
Paso 4) Como v2
1v2
2 /∈ A(T2), entonces debemos pasar al paso siguiente.
Paso 5) Como ninguna hoja de T2 es adyacente a algun vértice de V ∗, en-
tonces pasamos al paso siguiente.
Paso 6) Como Domi2(T2 − x) ⊂ Domi2(T2) con x ∈ Hojas(T2), entonces
consideramos el 2-árbol siguiente:
T3 ∼ T2 + P,
como se muestra en la Figura 3.41, donde P es una (x, w2)-trayectoria
tal que x ∈ Hojas(T2).
Figura 3.41: T3 ∼ T2 + P .
Paso 2) Como T3 es un 2-árbol que 2-domina a G; el proceso termina.
Entonces T3 es el 2-árbol que 2-domina a G, por lo que se garantiza que el
servicio de distribución de agua potable mantiene la presión mínima para
todos los usuarios, pues en cada vertice del ramal se coloca una bomba
de agua.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE127
Solución 2.- Veamos la solución para m = 2, n = 2 y k = 3. Como vimos an-
teriormente se tiene lo siguiente para la condición del Teorema 3.2.1:
α2(2+1)(G) ≤ (3 − 1)2 + 1, por lo que α6(G) = 3 < 5. Por lo tanto,
G tiene un 3-árbol 2-dominante, el cual lo encontraremos mediante el
algoritmo.
Paso 1) Tomamos a T un árbol de orden 2 en G como se muestra en la
Figura 3.42.
Figura 3.42: T de orden 2.
Paso 2) Como T no 2-domina a G, entonces existe un vértice w en
V (G) − Domi2(T ) y consideremos a V ∗ = {v1, v2} tal que
V ∗ ⊂ V (G) como se muestra en la Figura 3.43.
Figura 3.43: T .
128 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Paso 3) Como δT (v1) = δT (v2) = 1, entonces tomemos a Q2 la
(v2, w)-trayectoria y consideremos a T1 ∼ T + Q2 como se muestra
en la Figura 3.44, el cual es un 2-árbol pues se tiene que ∆G(T2) = 2.
Figura 3.44: T1 ∼ T + Q2.
Paso 2) Como T1 no 2-domina a G, entonces existe un vértice w1 en
V (G) − Domi2(T1) y consideremos a V ∗
1 = {v1
1, v1
2} tal que
V ∗
1 ⊂ V (T1) como se muestra en la Figura 3.45.
Figura 3.45: T1.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE129
Paso 3) Como δT1
(v1
1) = δT1
(v1
2) = 2 < 3, entonces tomemos a Q2 la (v1
2, w1)-
trayectoria y consideremos a T2 ∼ T1 + Q2 como se muestra en la
Figura 3.46, el cual es un 3-árbol pues se tiene que ∆G(T2) = 3.
Figura 3.46: T2 ∼ T1 + Q2.
Paso 2) Como T2 no 2-domina a G, entonces existe un vértice w2 en
V (G) − Domi2(T2) y consideremos a V ∗
2 = {v2
1, v2
2} tal que
V ∗
2 ⊂ V (T2) como se muestra en la Figura 3.47.
Figura 3.47: T2.
130 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Paso 3) Como δT2
(v2
1) = 3 y δT2
(v2
2) = 2 < 3, entonces tomemos a Q2 la
(v2
2, w2)-trayectoria y consideremos a T3 ∼ T2 +Q2, como se muestra
en la Figura 3.48, el cual es un 3-árbol pues se tiene que ∆G(T2) = 3.
Figura 3.48: T3 ∼ T2 + Q2.
Paso 2) Como T3 no 2-domina a G, entonces existe un vértice w3 en
V (G) − Domi2(T3) y consideremos a V ∗
3 = {v3
1, v3
2} tal que
V ∗
3 ⊂ V (T3) como se muestra en la Figura 3.49. Además tenemos
un vértice yx en YHojas que cumple dG(yx, w) ≤ 2.
Figura 3.49: T3.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE131
Paso 3) Como δT3
(v3
1) = 3 y δT3
(v3
2) = 3, entonces pasamos al paso siguiente.
Paso 4) Como v3
1v3
2 /∈ A(T3), entonces pasamos al paso siguiente.
Paso 5) Como xv3
i /∈ A(T3) para i ∈ {1, 2} y alguna x ∈ Hojas(T3), entonces
pasamos al paso siguiente.
Paso 6) Como Domi2(T3 − {x}) ⊂ Domi2(T3) con x ∈ Hojas(T3), entonces
existe un vértice yx en YHojas que cumple dG(yx, w) ≤ 2, por lo que
por el paso 6 del algoritmo tomamos a P la (x, yx)-trayectoria y
consideremos a:
T4 ∼ T3 + P
como se muestra en la Figura 3.50, el cual es un 3-árbol pues se
tiene que ∆G(T4) = 3.
Figura 3.50: T4 ∼ T3 + P .
Paso 2) Como T4 2-domina a G; el proceso termina.
Entonces T4 es un 3-árbol que 2-domina a G, garantizando que de este
modo la presión mínima se mantenga en todos los vértices de G, pues se
coloca una bomba de agua en cada vértice del ramal.
132 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Solución 3.- Veamos la solución para m = 2, n = 2 y k = 4. Como vimos an-
teriormente se tiene lo siguiente para la condición del Teorema 3.2.1
α2(2+1)(G) ≤ (4 − 1)2 + 1, α6 = 3 < 7. Por lo tanto, G tiene un 4-árbol
2-dominante, el cual lo encontraremos mediante el algoritmo.
Paso 1) Tomamos a T un árbol de orden 2 en G como se muestra en la
Figura 3.51.
Figura 3.51: T de orden 2.
Paso 2) Como T no 2-domina a G, entonces existe un vértice w en
V (G) − Domi2(T ) y consideremos a V ∗ = {v1, v2} tal que
V ∗ ⊂ V (T ) como se muestra en la Figura 3.52.
Figura 3.52: T .
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE133
Paso 3) Como δT (v1) = δT (v2) = 1, entonces tomamos a Q2 la (v2, w)-trayectoria
y consideramos a T1 ∼ T +Q2 un árbol como se muestra en la Figura
3.53.
Figura 3.53: T1 ∼ T + Q2.
Paso 2) Como T1 no 2-domina a G, entonces existe un vértice w1 en
V (G) − Domi2(T1) y consideremos a V ∗
1 = {v1
1, v1
2} tal que
V ∗
1 ⊂ V (T1) como en la Figura 3.54.
Figura 3.54: T1.
134 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Paso 3) Como δT (v1
1) = 1 y δT (v1
2) = 2, entonces tomamos a Q2 la (v1
2, w1)-
trayectoria y consideramos a T2 ∼ T1 +Q2 un árbol como se muestra
en la Figura 3.55.
Figura 3.55: T2 ∼ T1 + Q2.
Paso 2) Como T2 no 2-domina a G, entonces existe un vértice w2 en
V (G) − Domi2(T2) y consideremos a V ∗
2 = {v2
1, v2
2} tal que
V ∗
2 ⊂ V (T2) como se muestra en la Figura 3.56.
Figura 3.56: T2.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE135
Paso 3) Como δT2
(v2
1) = 1 y δT2
(v2
2) = 3, entonces tomamos Q2 la (v2
2, w2)-
trayectoria y consideramos a T3 ∼ T2 +Q2 un árbol como se muestra
en la Figura 3.57.
Figura 3.57: T3 ∼ T2 + Q2.
Paso 2) Como T3 no 2-domina a G, entonces existe un vértice w3 en
V (G) − Domi2(T3) y consideremos a V ∗
3 = {v3
1, v3
2} tal que
V ∗
3 ⊂ V (T3) como se muestra en la Figura 3.58.
Figura 3.58: T3.
136 CAPÍTULO 3. K-ÁRBOLES M -DOMINANTES EN GRÁFICAS
Paso 3) Como δT3
(v3
2) = 4 ya no podemos agregarle una arista adicional
sin exceder el grado máximo deseado para el árbol y por otro lado
tenemos que δT3
(v3
1) = 2, entonces tomamos a T4 ∼ T3 +Q1 un árbol
como se muestra en la Figura 3.59.
Figura 3.59: T4 ∼ T3 + Q1.
Paso 2) Como T4 no 2-domina a G, entonces existe un vértice w4 en
V (G) − Domi2(T4) y consideremos a V ∗
4 = {v4
1, v4
2} tal que
V ∗
4 ⊂ V (T4) como se muestra en la Figura 3.60.
Figura 3.60: T4.
3.3. APLICACIÓN SOBRE UNA RED DE DISTRIBUCIÓN DE AGUA POTABLE137
Paso 3) Como δT4
(v4
2) = 4, no es posible agregar una trayectoria que incida
en v4
2 sin exceder el grado máximo deseado, por otro lado δT4
(v4
1) = 3,
entonces tomamos a T5 ∼ T4 + Q1 un árbol como se muestra en la
Figura 3.61.
Figura 3.61: T5 ∼ T4 + Q1.
Paso 2) Como T5 2-domina a G; el proceso termina.
Entonces T5 es un 4-árbol que 2-domina a G, con lo que se garantiza que
la presión mínima se mantenga en todos los vértices de la gráfica G, pues
se coloca una bomba de agua en cada vértice del ramal.
De las soluciones 1, 2 y 3 obtuvimos árboles que 2-dominan a G, por lo que
se distribuye el agua con la presión mínima deseada en todos los puntos de
nuestra gráfica G. Observemos que en la primera solución el 2-árbol encon-
trado tiene 18 vértices de G, en la segunda el 3-árbol tiene 15 y por último el
4-árbol tiene 21, por lo que el 3-árbol es la solución que se recomienda por
ser la que tiene menos vértices de G. Sabiendo esto colocaremos una bom-
ba en cada vértice del ramal de alta presión para garantizar la distribución
mínima en toda la red.
Conclusiones
A lo largo de esta tesis estudiamos a los k-árboles como subgráficas de gráficas n-
conexas con ciertas condiciones de independencia. Primero observamos que para encon-
trar un 2-árbol generador en una gráfica n-conexa esta debía cumplir que α(G) ≤ n+1.
Seguido de esto, examinamos en el capítulo 2, que para tener un
k-árbol generador de una gráfica n-conexa, esta debe cumplir que;
α(G) ≤ 1 + n(k − 1).
Posteriormente a lo largo del capítulo 3, notamos que para encontrar un k-árbol
m-dominante en una gráfica n-conexa; esta satisface que; α2(m+1)(G) ≤ (k − 1)n + 1.
Finalmente, de la prueba del capítulo 3 se construyó un algoritmo para encontrar un
k-árbol m-dominante en una gráfica n conexa con α2(m+1)(G) ≤ (k −1)n+1; queda por
analizar si este algoritmo es eficiente. Luego, dimos una posible solución al problema de
distribución de agua en una red pequeña, queda por resolver; si el k-árbol m-dominante
encontrado es una solución óptima.
Algunos puntos por estudiar a futuro son:
¿Cómo podemos encontrar un k-árbol m-dominante de cardinalidad mínima?
¿Cuántos k-árboles m-dominantes distintos hay en G una gráfica n-conexa con
α2(m+1)(G) ≤ (k − 1)n + 1 para una misma k?
138
Bibliografía
[1] Biggs, N. Lloyd, E. Wilson, R,(1986) Graph Theory, 1736–1936, Oxford Uni-
versity Press.
[2] Bollobás, B. Riordan, O.M. (2003), Mathematical results on scale-free ran-
dom graphs in “Handbook of Graphs and Networks". (S. Bornholdt and H.G. Schus-
ter (eds)), Wiley VCH, Weinheim, 1st ed.
[3] Bondy, J.A. Murty, U.S.R. (2008) Graph Theory, Springer, ISBN 978-1-84628-
969-9.
[4] Bondy, J. A. Murty U.S.R. (1982) Graph Theory With Applications. Depart-
ment of Combinatorics and Optimization, Uniuersity of Waterloo, Ontario, Cana-
da.
[5] Broersma H. J. (1988), Existence of ∆k-cycles and ∆k-paths, J. Graph Theory
12 499-507.
[6] Chartrand, G. (1985) Introductory Graph Theory, Dover, ISBN 0-486-24775-9.
Graphs and Digraphs, Fifth Edition.
[7] Chartrand G. Linda L. Ping Z. Graphs and Digraphs, October 19, 2010 by
Chapman and Hall/CRC Textbook - 598 Pages - 340 B/W ISBN 9781439826270
- CAT# K11263 H.J.
[8] Comisión Nacional del Agua, Manual de Agua Potable, Alcantarillado y Sa-
neamiento, Diciembre 2007.
[9] Chvátal V. Erdös P. A note on hamiltonian circuits, Discrete Math. 2 (1972)
111-113.
[10] Diestel, Reinhard, Graph Theory Electronic Edition 2010. http://diestel-
graph-theory.com/
[11] Goldfeder, Ilán A. Una introducción a la Teoría de las Gráficas (Versión preeli-
minar). http://www.matem.unam.mx/ilan/
139
140 BIBLIOGRAFÍA
[12] Mikio K. Kenta O. Masao T. Guiying Y., m-dominating k-trees of graphs.
Discrete Mathematics 339 (2016) 729–736
[13] Neumann-Lara, V. Rivera-Campo, E. Spanning tree with bounded degrees,
Combinatorica 11 (1991) 55-61.
[14] Tutte, W.T. (2001), Graph Theory, Cambridge University Press, p. 30, ISBN
978-0-521-79489-3.
[15] Win, S. On a conjecture of Las Vergnas concerning certain spanning trees in
graphs. Resultate der Mathematik, 2, 215-224.