tesis

El grafo de línea de un grafo G = (V (G),E(G)), denotado por L(G), es el grafo que
tiene como vértices las aristas de G, es decir, V (L(G)) = E(G) y en el cual dos vértices
x, y de L(G) sonadyacentes, si como aristas de G son incidentes, esto es, x e y en G
tienen un extremo en común.
Un grafo es hamiltoniano-conexo si entre cada par de vértices del grafo existe una
cadena hamiltoniana quelos une. Una cadena dominante de un grafo G es una cadena
simple a la cual le inciden todos los lados de G si además contiene todos los vértices
del grafo es denominada dominante generadora. Ungrafo G es dominante si entre cada
par de lados de G existe una cadena dominante y si entre cada par de lados de G existe
una cadena dominante generadora es denominado dominante generador.
En el año1985 C. Thomassen [1] da la siguiente conjetura.
"Todo grafo de línea 4-conexo es hamiltoniano".
Esta conjetura es consecuencia de haber probado en el año 1981 por el mismo Thomassen
[3] que todografo de línea 4-conexo por lados es hamiltoniano. Además, en el año 1986
Siming Shan en [10] probó que si G es 4-conexo por lados entonces el grafo de línea
L(G) es hamiltoniano-conexo. El resultadoprincipal de este trabajo, también dado por
Siming Shan [11] es el siguiente teorema.
"Todo grafo de línea 7-conexo es hamiltoniano-conexo".
Este trabajo consta de tres capítulos:
En el capítulo 1daremos las definiciones básicas de la teoria de grafos necesarias en
el desarrollo de este trabajo.
En el capítulo 2 definiremos grafos hamiltonianos y grafos de línea.
En el capítulo 3presentaremos la demostración de que todo grafo de línea 7-conexo es
hamiltoniano-conexo.
1

Capítulo 1
PRELIMINARES
En este capítulo daremos algunos conceptos básicos de la teoría de grafos los cualesson necesarios para el desarrollo de este trabajo.
§1.1. Terminología básica
Definición 1.1.1. Un k−subconjunto de un conjunto C es un subconjunto de C que
tiene k elementos.
Ejemplo 1.1.1....