1 |
Ciclos hamiltonianos em produtos cartesianos de grafosPucohuaranga, Jorge Luis Barbieri January 2015 (has links)
Orientador: Prof. Dr. Letícia Rodrigues Bueno / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / Given a graph G, the hamiltonian cycle problem consists in determining if there is a cycle
containing all vertices of G exactly once. This problem is known to be NP-Complete,
therefore a recent trend is to searching for long cycles in order to determine the cycle with
the largest possible number of vertices. Another trend is searching for related structures.
In this aspect, being prism-hamiltonian has been an interesting relaxation of being hamiltonian.
The prism over a graph G consists of two copies of G with an edge joining the
corresponding vertices. A graph G is prism-hamiltonian if the prism over G contains a
hamiltonian cycle. In this work, we study a conjecture which claims that every 4-connected
4-regular graph is prism-hamiltonian. We prove the conjecture for claw-free graphs. In
fact, for a subclass of claw-free 4-connected 4-regular graphs, we prove a stronger result: its
hamiltonicity; therefore, corroborating to another conjecture from 1993 which states that
claw-free 4-connected 4-regular graphs are hamiltonian. Given a graph G, let G1 = GK2
and Gq = Gq..1K2, for q > 1. For every connected graph G, we prove that Gq is
hamiltonian for q dlog2 (G)e, where (G) is the maximum degree of G.
|
Page generated in 0.6702 seconds