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.
| Identifer | oai:union.ndltd.org:IBICT/oai:BDTD:77596 |
| Date | January 2015 |
| Creators | Pucohuaranga, Jorge Luis Barbieri |
| Contributors | Bueno, Letícia Rodrigues, Martin, Daniel Morgato, Mendonça Neto, Candido Ferreira Xavier de |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf, 59 f. : il. |
| Source | reponame:Repositório Institucional da UFABC, instname:Universidade Federal do ABC, instacron:UFABC |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=77596&midiaext=71066, http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=77596&midiaext=71065, Cover: http://biblioteca.ufabc.edu.brphp/capa.php?obra=77596 |
Page generated in 0.0024 seconds