Universidade Federal do ABC
Centro de Matemática, Computação e Cognição (CMCC)
Curso de Pós-Graduação em Ciência da Computação
Dissertação
Jorge Luis Barbieri Pucohuaranga
CICLOS HAMILTONIANOS EM PRODUTOS CARTESIANOS DE GRAFOS
Santo André - SP
2014
Curso de Pós-Graduação em Ciência da Computação
Dissertação
Jorge Luis Barbieri Pucohuaranga
CICLOS HAMILTONIANOS EM PRODUTOS CARTESIANOS DE GRAFOS
Trabalho apresentado como requisito
parcial para obtenção do tı́tulo de
Mestre em Ciência da Computação, sob
orientação da Professora Doutora Letı́cia Rodrigues Bueno.
Santo André - SP
2014
Este exemplar foi revisado e alterado em relação à versão
original, de acordo com as observações levantadas pela banca no
dia da defesa, sob responsabilidade única do autor e com a
anuência de sua orientadora.
Santo André, 26 de maio de 2014.
Assinatura do autor:
Assinatura da orientadora:
Jorge Luis Barbieri Pucohuaranga
CICLOS HAMILTONIANOS EM PRODUTOS CARTESIANOS DE GRAFOS
Essa Dissertação foi julgada e
aprovada para a obtenção do grau
de Mestre em Ciência da Computação no
curso de Pós-Graduação em Ciência da
Computação da Universidade Federal
do ABC.
BANCA EXAMINADORA
Profa. Dra. Letı́cia Rodrigues Bueno
CMCC/UFABC
Prof. Dr. Candido Ferreira Xavier de Mendonça Neto
EACH/USP
Prof. Dr. Daniel Morgato Martin
CMCC/UFABC
Prof. Dr. Ademir Aparecido Constantino
DIN/UEM
Prof. Dr. Rodrigo de Alencar Hausen
CMCC/UFABC
Santo André - SP
2014
i
Este trabalho contou com auxı́lio financeiro da Universidade Federal do ABC - UFABC
(bolsa de mestrado, institucional), de junho/2012 a janeiro/2014 e da Coordenação de
Aperfeiçoamento de Pessoal de Nı́vel Superior - CAPES (bolsa de mestrado, demanda
social), de fevereiro/2014 a maio/2014.
ii
Dedico aos meus pais Jorge Jesús e Esther
Luzmila, e aos meus irmãos Luis Gustavo e
Marı́a Alessandra.
iii
Agradecimentos
A toda minha famı́lia pelo constante apoio e incentivo que sempre me derem em todo
momento. Em especial, aos meus pais Jorge e Esther, aos meus irmãos Gustavo e Marı́a
Alessandra e a minha avó Teresa pelas orações.
A minha orientadora Letı́cia Rodrigues Bueno, pelo apoio, paciência, amizade e por
ser a primeira pessoa que acreditou nas minhas possibilidades para realizar esse trabalho,
Aos professores do Centro de Matemática, Computação e Cognição (CMCC), especialmente aos professores Wagner, Daniel, Ronaldo, Harlem, Claudio, Jesús pela importância
na minha formação como mestre.
Aos membros da banca na minha qualificação, os professores, Daniel Morgato Martin e
Jai Donadelli Junior, os seus conselhos foram muito importantes para a culminação deste
trabalho.
A UFABC e a Capes pelo apoio financeiro.
Agradeço também a todos os amigos e colegas que conheci durante esses dois anos.
Emfim, a todos que de alguma maneira contribuı́ram na realização deste trabalho. Muchas
gracias.
iv
Resumo
Dado um grafo G, o problema do ciclo hamiltoniano consiste em determinar se existe
um ciclo que passa por todos os vértices de G exatamente uma vez. Devido à dificuldade
inerente a um problema NP-Completo, uma tendência recente tem sido procurar por ciclos
longos, buscando determinar o ciclo com o maior número de vértices possı́vel. Outra
tendência consiste na busca por estruturas relacionadas. Neste aspecto, ser um grafo
prisma-hamiltoniano tem se mostrado ser uma relaxação interessante de ser hamiltoniano.
O prisma de um grafo G consiste em duas cópias de G com uma aresta unindo cada
par de vértices correspondentes. Se o prisma de G contém um ciclo hamiltoniano então
G é prisma-hamiltoniano. Neste trabalho estudamos uma conjectura que afirma que
todo grafo 4-regular 4-conexo é prisma-hamiltoniano. Provamos essa conjectura para
grafos livres de garras. De fato, para uma subclasse dos grafos 4-regulares 4-conexos
livres de garras, provamos um resultado mais forte: sua hamiltonicidade; corroborando
assim com outra conjectura de 1993 que afirma que grafos 4-regulares 4-conexos livres de
garras são hamiltonianos. Dado um grafo G, seja G1 = GK2 e Gq = Gq−1 K2 , para
q > 1. Mostramos que, para todo grafo conexo G, temos que Gq é hamiltoniano para todo
q ≥ dlog2 ∆(G)e, onde ∆(G) é o grau máximo de G.
v
Abstract
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−1 K2 , 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.
Lista de Figuras
1.1
Um ciclo hamiltoniano no dodecaedro. . . . . . . . . . . . . . . . . . . . .
1
1.2
Um caminho hamiltoniano no grafo de Petersen. . . . . . . . . . . . . . . .
2
1.3
Um grafo G e um ciclo hamiltoniano no prisma de G. . . . . . . . . . . . .
2
2.1
União de Grafos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Grafo Completo K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Os grafos bipartidos completos K1,3 e K2,3 . . . . . . . . . . . . . . . . . . .
6
2.4
Grafos estrela para n = 3, 4 e 5. . . . . . . . . . . . . . . . . . . . . . . . .
6
2.5
Os grafos n-cubo para n = 1, 2, 3. . . . . . . . . . . . . . . . . . . . . . . .
8
2.6
O produto cartesiano de C4 e do K2 . . . . . . . . . . . . . . . . . . . . . .
9
2.7
O prisma sobre o grafo completo K5 . . . . . . . . . . . . . . . . . . . . . . 10
2.8
Um ciclo hamiltoniano no prisma de G construı́do a partir de um caminho
hamiltoniano em G. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.9
O grafo K2,4 é prisma-hamiltoniano, mas K2,4 não tem uma 2-árvore. . . . 11
2.10 Um exemplo de um grafo G que tem um 2-passeio mas não é prismahamiltoniano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.11 Um cacto par. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1
Exemplos de um EP-subgrafo e de um SEEP-subgrafo. . . . . . . . . . . . 15
3.2
A contração de um triângulo. . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.1
O produto cartesiano entre C4 e C8 . . . . . . . . . . . . . . . . . . . . . . . 21
4.2
Ilustração da prova do Lema 26. . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3
O produto S4 K22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
vi
LISTA DE FIGURAS
vii
5.1
Exemplos de grafos 4-regulares 4-conexos. . . . . . . . . . . . . . . . . . . 26
5.2
Um caminho hamiltoniano no grafo de Meredith. . . . . . . . . . . . . . . 27
5.3
Um grafo 4-regular 4-conexo bipartido não hamiltoniano. . . . . . . . . . . 27
5.4
Exemplos de dois grafos em G1 . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.5
Exemplos de dois grafos em G2 . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.6
Grafo em G com r = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.7
Remoção de K4 (m) no Caso 1. . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.8
Construção de um ciclo hamiltoniano para o Caso 1 do Teorema 41 . . . . 31
5.9
Construção de G0 para o caso 2 do Teorema 41. . . . . . . . . . . . . . . . 32
5.10 Construção de um ciclo hamiltoniano para o Caso 2 do Teorema 41. . . . . 33
5.11 Construção de G0 para o Caso 3 do Teorema 41. . . . . . . . . . . . . . . . 34
5.13 Construção de um ciclo hamiltoniano para o Caso 3(iii) do Teorema 41. . . 35
5.12 Construção de um ciclo hamiltoniano para o Caso 3 do Teorema 41. . . . . 36
5.14 Análise do Caso 4(i) do Teorema 41. . . . . . . . . . . . . . . . . . . . . . 37
5.15 Construção de G0 para o Caso 4(ii) do Teorema 41. . . . . . . . . . . . . . 38
Lista de Teoremas
1
Proposição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2
Proposição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3
Proposição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
4
Teorema (König, 1916 [16])
. . . . . . . . . . . . . . . . . . . . . . . . . .
7
5
Teorema (Euler, 1736 [8]) . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
6
Teorema (Whitney, 1932 [30]) . . . . . . . . . . . . . . . . . . . . . . . . .
7
7
Teorema (Menger, 1927 [19]) . . . . . . . . . . . . . . . . . . . . . . . . . .
8
8
Teorema (Menger, 1927 [19]) . . . . . . . . . . . . . . . . . . . . . . . . . .
8
9
Teorema (Dirac, 1952 [6], Dirac, 1960 [7]) . . . . . . . . . . . . . . . . . . .
8
10
Teorema (Dirac, 1952 [6], Dirac, 1960 [7]) . . . . . . . . . . . . . . . . . . .
8
11
Teorema (Barnette e Rosenfeld, 1973 [27]) . . . . . . . . . . . . . . . . . . 13
12
Teorema (Barnette e Rosenfeld, 1973 [27]) . . . . . . . . . . . . . . . . . . 13
13
Teorema (Fleischner, 1974 [9]) . . . . . . . . . . . . . . . . . . . . . . . . . 14
14
Teorema (Paulraja, 1993 [23]) . . . . . . . . . . . . . . . . . . . . . . . . . 15
15
Teorema (Paulraja, 1993 [23]) . . . . . . . . . . . . . . . . . . . . . . . . . 17
16
Corolário (Paulraja, 1993 [23]) . . . . . . . . . . . . . . . . . . . . . . . . . 17
viii
LISTA DE TEOREMAS
ix
17
Teorema (Paulraja, 1993 [23]) . . . . . . . . . . . . . . . . . . . . . . . . . 17
18
Teorema (Paulraja, 1993 [23]) . . . . . . . . . . . . . . . . . . . . . . . . . 17
19
Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
20
Teorema (Čada et al., 2004 [5]) . . . . . . . . . . . . . . . . . . . . . . . . 18
21
Teorema (Petersen, 1891 [24]) . . . . . . . . . . . . . . . . . . . . . . . . . 18
22
Lema (Čada et al., 2004 [5]) . . . . . . . . . . . . . . . . . . . . . . . . . . 18
23
Teorema (Rosenfeld e Barnette, 1973 [27], Čada et al., 2004 [5]) . . . . . . 19
24
Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
25
Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
26
Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
27
Lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
28
Teorema (Čada et al., 2009 [4]) . . . . . . . . . . . . . . . . . . . . . . . . 23
29
Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
30
Corolário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
31
Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
32
Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
33
Conjectura (Nash-Williams, 1971 [21]) . . . . . . . . . . . . . . . . . . . . 26
34
Conjectura (Kaiser et al., 2007 [13]) . . . . . . . . . . . . . . . . . . . . . . 27
35
Proposição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
36
Conjectura (Matthews e Summer, 1984 [17]) . . . . . . . . . . . . . . . . . 28
37
Conjectura (Plummer, 1993 [25]) . . . . . . . . . . . . . . . . . . . . . . . 28
LISTA DE TEOREMAS
x
38
Teorema (Plummer, 1995 [26]) . . . . . . . . . . . . . . . . . . . . . . . . . 28
39
Teorema (Plummer, 1995 [26]) . . . . . . . . . . . . . . . . . . . . . . . . . 29
40
Teorema (Plummer, 1995 [26]) . . . . . . . . . . . . . . . . . . . . . . . . . 29
41
Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
42
Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
43
Teorema (Plummer, 1995 [26]) . . . . . . . . . . . . . . . . . . . . . . . . . 37
44
Teorema (Kaiser et al., 2007 [13]) . . . . . . . . . . . . . . . . . . . . . . . 37
45
Corolário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
46
Corolário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Sumário
Lista de Figuras
vii
Lista de Teoremas
x
1 Introdução
1
2 Fundamentação Teórica
3
2.1
Definições em Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2
O Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3 Classes de Grafos Prisma-Hamiltonianos
14
3.1
Grafos bipartidos 2-conexos de grau máximo 2 ou 3 . . . . . . . . . . . . . 14
3.2
Grafos 3-regulares 3-conexos . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Outros Produtos Cartesianos de Grafos
21
5 Grafos 4-regulares 4-conexos
26
5.1
Grafos 4-regulares 4-conexos livres de garras . . . . . . . . . . . . . . . . . 28
6 Conclusões
39
Referências Bibliográficas
40
xi
Capı́tulo 1
Introdução
Um dos problemas mais estudados em Teoria dos Grafos foi proposto por William Rowan
Hamilton em 1859 sendo, no começo, apenas um jogo matemático. Tratava-se da busca de
um ciclo que passa exatamente uma vez por cada vértice de um dodecaedro (Figura 1.1).
O problema de determinar a existência de um ciclo hamiltoniano em um grafo, ou seja, um
ciclo que percorre todos os vértices de um grafo e volta ao vértice inicial, ficou conhecido
como o Problema do Ciclo Hamiltoniano (”Hamiltonian Cycle Problem” - HCP, em inglês).
Em 1972, Karp [15] mostrou que o problema de decisão associado ao HCP é NP-completo.
Figura 1.1: Um ciclo hamiltoniano no dodecaedro.
Uma variação do HCP é o Problema do Caminho Hamiltoniano (”Hamiltonian Path
Problem” - HPP, em inglês) que consiste na busca de um caminho que passa por todos os
pontos exatamente uma vez. É fácil notar que, se um grafo G tem um ciclo hamiltoniano
C, obtemos um caminho hamiltoniano em G simplesmente removendo uma aresta do ciclo
C. Porém, um grafo com um caminho hamiltoniano não necessariamente possui um ciclo
hamiltoniano como, por exemplo, o grafo de Petersen (Figura 1.2). Assim como o HCP,
o problema de decisão associado ao HPP é NP-Completo [10].
Devido à dificuldade inerente a um problema NP-Completo, uma tendência recente
tem sido procurar por ciclos longos, buscando determinar o ciclo com o maior número
de vértices possı́vel. Outra tendência tem sido buscar por estruturas relacionadas. Neste
1
CAPÍTULO 1. INTRODUÇÃO
2
Figura 1.2: Um caminho hamiltoniano no grafo de Petersen.
aspecto, ser prisma-hamiltoniano tem se mostrado ser uma relaxação interessante de ser
hamiltoniano. O prisma de um grafo G consiste em duas cópias de G com uma aresta
unindo os vértices correspondentes (Figura 1.3). Dizemos que G é prisma-hamiltoniano
se o prisma de G contém um ciclo hamiltoniano (Figura 1.3(b))
(a) G
(b) O prisma de G e um ciclo hamiltoniano
Figura 1.3: Um grafo G e um ciclo hamiltoniano no prisma de G.
Já foi provado que grafos 3-regulares 3-conexos são prisma-hamiltonianos [23]. Neste
trabalho, estudamos uma conjectura de Kaiser et al. [13] que afirma que todo grafo 4regular 4-conexo é prisma-hamiltoniano. Provamos a conjectura de Kaiser et al. [13] para
os grafos livres de garras.
Dado um grafo G, seja G1 = GK2 e Gq = Gq−1 K2 , para q > 1. Provamos também
que, para todo grafo conexo G, temos que Gq é hamiltoniano para todo q ≥ dlog2 ∆(G)e,
onde ∆(G) é o grau máximo do grafo G.
No Capı́tulo 2, apresentamos conceitos básicos em teoria dos grafos e o estado da
arte para o problema estudado. No Capı́tulo 3, estudamos as provas de alguns resultados
relacionados existentes na literatura. Nos Capı́tulos 4 e 5, apresentamos nossos resultados
e o Capı́tulo 6 apresenta as conclusões.
Capı́tulo 2
Fundamentação Teórica
Neste capı́tulo apresentamos as definições básicas em Teoria dos Grafos (Seção 2.1) utilizadas ao longo do texto. Na Seção 2.2 apresentamos o estado da arte do problema
estudado.
2.1
Definições em Grafos
Dados um inteiro não-negativo k e um conjunto X, dizemos que Y é k-subconjunto de X
se Y ⊆ X e |Y | = k, ou seja, se Y for um subconjunto de X e se Y possuir exatamente k
elementos. Denotamos por Xk a famı́lia de todos os k-subconjuntos de X.
Um grafo G é um tripla ordenada G = (V (G), E(G), ψG ) onde V (G) é um conjunto
finito e não vazio de pontos chamados vértices, E(G) é um conjunto finito de arestas e
ψG : E(G) → V (G)
é uma função de incidência que associa a cada aresta e de G um par de
2
vértices u e v (não necessariamente distintas), notação ψG (e) = {u, v} (ou ψG (e) = {v, u}
onde a ordem não é importante). Se u, v são vértices de um grafo e e = {u, v} é uma
aresta desse grafo, dizemos que u e v são vértices adjacentes ou extremos de e. Também
dizemos que a aresta e é incidente em u e em v. Por motivos de simplicidade na notação,
denotamos também a aresta {u, v} como uv.
Um grafo possui arestas paralelas ou múltiplas se tem arestas diferentes compartilhando os mesmos extremos. Se o grafo admite arestas e = uv com u = v, então dizemos
que o grafo contém laços. Um grafo é simples se não contém laços nem arestas múltiplas.
Neste trabalho chamaremos os grafos simples de grafos. Um grafo é trivial, se tem apenas
um vértice. A qualquer outro grafo chamaremos de não trivial.
A união de dois grafos G1 e G2 , denotado por G1 ∪ G2 , é o grafo cujo conjunto de
vértices é V (G1 ) ∪ V (G2 ) é o conjunto de arestas é E(G1 ) ∪ E(G2 ), veja um exemplo na
Figura 2.1.
3
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
(a) G1
(b) G2
4
(c) G1 ∪ G2
Figura 2.1: União de Grafos.
Dois grafos G e H são isomorfos se existe uma função bijetora φ : V (G) → V (H) tal
que φ(u)φ(v) ∈ E(H) ⇔ uv ∈ E(G) e, neste caso, dizemos que φ é um isomorfismo entre
G e H.
Um automorfismo de um grafo G é um isomorfismo entre G e G, o qual pode ser
considerado uma permutação α de V (G) que preserva a adjacência: uv ∈ E(G) se e
somente se α(u)α(v) ∈ E(G).
Dizemos que um grafo G é vértice-transitivo se, para todo par de vértices u, v ∈ V (G),
existe um automorfismo α que mapeia u em v. Dizemos que um grafo G é aresta-transitivo
se, para todo par de arestas uv, xy ∈ E(G), existe um automorfismo α tal que α(u)α(v) =
xy. Um grafo vértice e aresta-transitivo é um grafo simétrico.
Um grafo H é um subgrafo de um grafo G, denotado por H ⊆ G, se V (H) ⊆ V (G)
e E(H) ⊆ E(G). Também dizemos que H 0 é um subgrafo de G se existe um subgrafo H
de G tal que H e H 0 são isomorfos. Dois grafos G e H são idênticos se G é subgrafo de
H e, se H é subgrafo de G. Dizemos que H é um subgrafo próprio de G, denotado por
H ( G, se H é subgrafo de G onde |V (H)| < |V (G)| ou |E(H)| < |E(G)|. Um subgrafo
H de um grafo G é chamado de subgrafo gerador se V (H) = V (G).
Seja V 0 um subconjunto não vazio de V (G), dizemos que um subgrafo de G é o subgrafo
induzido por V 0 , denotado por G[V 0 ], se V (G[V 0 ]) = V 0 e E(G[V 0 ]) é o conjunto das
arestas de G que têm os dois extremos em V 0 . Também denotamos o subgrafo induzido
G[V (G)\V 0 ] por G − V 0 . Seja E 0 um subconjunto não vazio de E(G). Denotamos por
G − E 0 o subgrafo gerador de G cujo conjunto de arestas é E(G)\E 0 ; ou seja, o subgrafo
obtido ao remover as arestas E 0 de G.
Seja P uma propriedade qualquer de um grafo G. Dizemos que H ⊆ G é maximal
relativo à propriedade P se não existe um subgrafo H 0 ⊆ G que possui a propriedade P
onde H ( H 0 . A definição não implica necessariamente que H seja o maior subgrafo de
G com a propriedade P . Quando isso ocorre, o subgrafo H é dito ser máximo relativo a
propriedade P .
A vizinhança de um vértice v em um grafo G, denotado por N (v), é o conjunto de
vértices adjacentes a v. O grau de um vértice v, denotado por d(v), é o número de vértices
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
5
de G adjacentes a v, ou seja, d(v) = |N (v)|.
Proposição 1. Todo grafo G satisfaz
X
d(v) = 2|E(G)|.
v∈V (G)
A propriedade a seguir é um corolário da Proposição 1 e foi provado em [1].
Proposição 2. Em qualquer grafo, o número de vértices de grau ı́mpar é par.
O grau mı́nimo de um grafo G é denotado por δ(G). O grau máximo de um grafo G
é denotado por ∆(G). Se δ(G) = ∆(G) = k, dizemos que G é um grafo k-regular, ou
seja, todos os vértices de G tem grau k. Um grafo 3-regular é também chamado de grafo
cúbico.
Dizemos que um grafo com n vértices é completo, denotado por Kn , se todos seus pares
de vértices são adjacentes. A Figura 2.2 mostra o grafo completo em cinco vértices K5 .
Figura 2.2: Grafo Completo K5 .
Um grafo G é bipartido se existe uma partição de V (G) em dois subconjuntos V1 e V2
tal que toda aresta e ∈ E(G) tem exatamente um extremo em V1 e um extremo em V2 .
Um grafo bipartido completo, denotado por Kn,m , tem |V (G)| = n + m, |V1 | = n, |V2 | = m
e, para todo vértice v ∈ V1 , vale que N (v) = V2 . A Figura 2.3 mostra os grafos bipartidos
completos K1,3 e K2,3 . O grafo K1,3 é também chamado de garra (“claw”, em inglês)
(Figura 2.3(a)). Um grafo é livre de garra (“claw-free”, em inglês) se não contém uma
garra como subgrafo induzido.
Chamamos de estrela ao grafo bipartido completo K1,n . Denotamos o grafo estrela
K1,n de Sn . A Figura 2.4 mostra as estrelas S3 , S4 e S5 . Note que o grafo estrela é
aresta-transitivo e que a estrela S3 é uma garra.
Um passeio, de u a v, em um grafo G é uma sequência de vértices e arestas P =
(u = v1 , e1 , v2 , . . . , vk−1 , ek−1 , vk , ek , vk+1 = v), onde as arestas ei têm extremos vi e vi+1 ,
para 1 ≤ i ≤ k. O comprimento de um passeio é o número de seus vértices. Em
um grafo simples, um passeio é determinado pela sequência (v1 , v2 , . . . , vk , vk+1 ) de seus
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
(a) K1,3
6
(b) K2,3
Figura 2.3: Os grafos bipartidos completos K1,3 e K2,3 .
(a) S3
(b) S4
(c) S5
Figura 2.4: Grafos estrela para n = 3, 4 e 5.
vértices; consequentemente, usaremos a partir de agora essa notação. Os vértices vi , com
2 ≤ i ≤ k, são chamados de vértices internos do passeio. Os vértices u e v são chamados
de extremos do passeio e, nesse caso, dizemos que ele é um (u, v)-passeio. Se u = v
dizemos que P é um passeio fechado, caso contrário, P é um passeio aberto.
Um caminho é um passeio que não repete vértices, e chamamos de (u, v)caminho, a qualquer caminho de extremos u e v. E, um ciclo é um passeio fechado
(v1 , v2 , . . . , vk , vk+1 ), tal que k ≥ 3 e, os vértices vi para 1 ≤ i ≤ k são diferentes. Um
caminho de comprimento k é denotado por Pk e, um ciclo de comprimento k é denotado
por Ck .
Dizemos que a distância entre um par de vértices u e v em um grafo G, denotado por
dG (u, v), é o comprimento do caminho mais curto entre u e v em G.
Se um caminho contém todos os vértices de um grafo dizemos que é um caminho
hamiltoniano. Similarmente, um ciclo é hamiltoniano se contém todos os vértices do
grafo.
Chamamos de trilha um passeio que não repete arestas. Uma trilha euleriana de um
grafo G é uma trilha que passa por todas as arestas de G. Uma trilha euleriana fechada é
um passeio fechado que passa por cada aresta do grafo exatamente uma vez. Um grafo G é
euleriano se G contém uma trilha euleriana fechada. Uma condição necessária e suficiente
para um grafo ser euleriano é apresentada no Teorema 5.
Um grafo G é conexo se para todo par de vértices u, v existe um (u, v)-caminho; caso
contrário, dizemos que G é desconexo. Um grafo conexo G é uma árvore se G não contém
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
7
ciclos. Um subgrafo T de um grafo G é uma árvore geradora de G, se T é uma árvore e
é um subgrafo gerador de G.
Da definição de grafo conexo é fácil ver que:
Proposição 3. Todo grafo conexo bipartido tem uma única bipartição.
Uma das caracterı́sticas mais amplamente conhecidas dos grafos bipartidos foi provada
por König [16] em 1916:
Teorema 4 (König, 1916 [16]). Um grafo G é bipartido se e somente se G não tem ciclos
de comprimento ı́mpar.
Existe um teorema que caracteriza grafos conexos eulerianos.
Teorema 5 (Euler, 1736 [8]). Um grafo conexo G é euleriano se e somente se todos seus
vértices tem grau par.
Um corte de vértices de um grafo G é um subconjunto de vértices V 0 , tal que G − V 0 é
desconexo. Um k-corte de vértices é um corte de vértices com k elementos. Dizemos que
o vértice v é um ponto de articulação se {v} é um 1-corte de vértices. Se G tem um par de
vértices não adjacentes, a conectividade κ(G) é o tamanho do menor k-corte de vértices
de G; em outro casso, κ(G) = V (G)−1. Dizemos que G é k-conexo se k ≤ κ(G). Dizemos
que um corte de vértices V 0 desconecta os vértices u e v se não existe um (u, v)-caminho
em G − V 0 .
Similarmente, definimos a conectividade de arestas. Um corte de arestas de G é um
subconjunto de arestas E 0 , tal que G − E 0 é desconexo. Um k-corte de arestas é um corte
de arestas com k elementos. Se {e} é 1-corte de arestas, então a aresta e é chamada de
ponte. Se G é não trivial, a conectividade em arestas, denotado por κ0 (G), é o tamanho
do menor k-corte de arestas. Se G é trivial, k 0 (G) = 0 . Dizemos que G é k-conexo em
arestas se k ≤ κ0 (G).
O Teorema 6 apresenta uma relação entre a conectividade em vértices, a conectividade
em arestas e o grau mı́nimo de um grafo.
Teorema 6 (Whitney, 1932 [30]). Seja G um grafo, então κ(G) ≤ κ0 (G) ≤ δ(G).
Dizemos que dois caminhos P e Q são internamente disjuntos se P e Q não tem vértices
internos em comum. Note que, se P e Q são (u, v)-caminhos internamente disjuntos, então
V (P ) ∩ V (Q) = {u, v}.
Apresentamos dois teoremas fundamentais em conectividade: o Teorema 7 estabelece
uma relação entre o corte de vértices e caminhos internamente disjuntos. O Teorema 8
estabelece que qualquer par de vértices u e v de um grafo k-conexo tem pelo menos k
caminhos internamente disjuntos conectando u a v.
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
8
Teorema 7 (Menger, 1927 [19]). Sejam s e t dois vértices não-adjacentes de um grafo,
então o número máximo de caminhos internamente disjuntos entre s e t é igual ao número
mı́nimo de vértices em um corte de vértices que desconecta s e t.
Teorema 8 (Menger, 1927 [19]). Um grafo G com |V (G)| ≥ k+1 é k-conexo se e somente
se para quaisquer dois vértices de G existem k caminhos internamente disjuntos.
Os Teoremas 9 e 10 foram provados por Dirac:
Teorema 9 (Dirac, 1952 [6], Dirac, 1960 [7]). Seja G um grafo 2-conexo com δ(G) = d.
Então G tem um ciclo de comprimento maior ou igual a min{|V (G)|, 2d}.
Teorema 10 (Dirac, 1952 [6], Dirac, 1960 [7]). Seja G é um grafo k-conexo com k ≥ 2.
Para todo conjunto S ⊆ V (G) com k vértices, existe um ciclo em G que inclui S no seu
conjunto de vértices.
Um n-cubo (ou cubo de dimensão n), denotado por Qn , é um grafo onde os vértices são todas as sequências de n bits e, onde dois vértices são adjacentes se e somente se diferem em exatamente um bit. Por exemplo, os vértices do 3-cubo são
000, 001, 010, 011, 100, 101, 110, 111 e o vértice 000 é adjacente somente aos vértices
001, 010 e 100, e assim por diante.
(a) Q1
(b) Q2
(c) Q3
Figura 2.5: Os grafos n-cubo para n = 1, 2, 3.
O produto cartesiano de dois grafos G e H é denotado por GH e tem como conjunto de vértices V (G) × V (H) e o conjunto de arestas é o conjunto de todos os pares
(u1 , v1 )(u2 , v2 ) tais que u1 u2 ∈ E(G) e v1 = v2 ou v1 v2 ∈ E(H) e u1 = u2 . Veja na
Figura 2.6 o produto cartesiano do C4 e do K2 .
Dizemos que L(G) é o grafo linha de G, onde V (L(G)) = E(G), e e1 , e2 ∈ E(G) são
adjacentes em L(G) se e1 e e2 são arestas adjacentes em G. Dizemos que um grafo H é
um grafo linha se existe um grafo G tal que H = L(G).
Uma cobertura de vértices por ciclos de um grafo G é um conjunto de ciclos de G
cuja união contém todos os vértices de G. Se os ciclos da cobertura não tem vértices em
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
(a) C4 e K2
9
(b) O grafo C4 K2
Figura 2.6: O produto cartesiano de C4 e do K2 .
comum, a cobertura é então uma cobertura de vértices por ciclos disjuntos e, neste caso,
o conjunto de ciclos consiste em um subgrafo gerador de G.
Um subconjunto M ⊆ E(G) é um emparelhamento de G se todo par de arestas de M
não é adjacente em G. Um emparelhamento M satura um vértice v, se existe uma aresta
em M incidente em v. Um emparelhamento M é chamado de emparelhamento perfeito
se, para todo vértice de G, existe uma aresta em M incidente a ele. Um emparelhamento
M é um emparelhamento máximo se, para todo emparelhamento M 0 de G, temos que
|M 0 | ≤ |M |. Claramente, todo emparelhamento perfeito é máximo.
Um k-fator de G é um subgrafo gerador k-regular de G. Dizemos que G é k-fatorável
se existem k-fatores disjuntos em arestas H1 , H2 , . . . , Hl tais que G = H1 ∪ H2 ∪ . . . ∪ Hl .
Observe que um 1-fator é um emparelhamento perfeito e um 2-fator é uma cobertura dos
vértices por ciclos disjuntos.
Na próxima seção, discutimos o estado da arte do problema estudado.
2.2
O Problema
Dado um grafo G, o problema de determinar se G tem um ciclo hamiltoniano é NPcompleto [15]. Da mesma forma, determinar se G tem um caminho hamiltoniano é NPcompleto [10]. Dada a dificuldade inerente aos problemas NP-completos, uma direção
adotada pelos pesquisadores consiste na busca por estruturas relacionadas.
Um k-passeio é um passeio gerador fechado onde cada vértice é visitado no máximo
k vezes e uma k-árvore é uma árvore geradora de grau máximo k. Portanto, um ciclo
hamiltoniano é um 1-passeio e um caminho hamiltoniano é uma 2-árvore. Jackson e
Wormald [12] provaram que um grafo com uma k-árvore tem um k-passeio e, se um grafo
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
10
G tem um k-passeio, então G tem uma (k + 1)-árvore, resultando na seguinte hierarquia:
1-passeio (ciclo hamiltoniano) =⇒ 2-árvore (caminho hamiltoniano) =⇒ 2-passeio
=⇒ 3-árvore =⇒ 3-passeio =⇒ · · ·
O prisma sobre um grafo G é o produto cartesiano GK2 . Um prisma sobre G pode
ser visto como um grafo obtido ao unir por meio de uma aresta os vértices correspondentes
de duas cópias de G. Veja, por exemplo, a Figura 2.7. Se o prisma sobre um grafo G tem
um ciclo hamiltoniano, então G é prisma-hamiltoniano.
Mais tarde, Kaiser et al. [13] mostraram que:
2-árvore =⇒ prisma-hamiltoniano =⇒ 2-passeio
(a) O grafo completo K5
(2.1)
(b) O prisma sobre K5
Figura 2.7: O prisma sobre o grafo completo K5 .
Portanto, grafos prisma-hamiltonianos estão mais “próximos” de serem hamiltonianos
que os grafos com apenas um 2-passeio.
Vamos analisar a Expressão 2.1. Se um grafo G tem um caminho hamiltoniano (2árvore), então construı́mos um ciclo hamiltoniano no prisma sobre G conectando o caminho hamiltoniano em cada cópia do grafo através de duas arestas (veja a Figura 2.8).
Por outro lado, um ciclo hamiltoniano no prisma sobre G não implica a existência de
um caminho hamiltoniano em G. Veja na Figura 2.9 que o prisma sobre o grafo K2,4
é hamiltoniano. No entanto, não existe um caminho hamiltoniano no grafo K2,4 , pois a
diferença entre o tamanho das bipartições é maior que 1.
Um grafo G ser prisma-hamiltoniano implica que G tem um 2-passeio porque, a partir
de um ciclo hamiltoniano C no prisma sobre G, podemos construir um 2-passeio, usando
a mesma ordem dos vértices de C. Por exemplo, na Figura 2.9 (b), a partir do ciclo
hamiltoniano (a, a0 , y 0 , d0 , d, y, c, c0 , x0 , b0 , b, x, a) no prisma sobre K2.4 , obtemos o 2-passeio
(a, y, d, y, c, x, b, x, a) em K2,4 . Por outro lado, a existência de um 2-passeio em G não
implica um ciclo hamiltoniano no prisma sobre G. Veja um exemplo na Figura 2.10,
onde G tem um 2-passeio (u1 , u2 , u3 , u4 , u5 , u4 , u6 , u7 , u6 , u8 , u2 , u1 ), mas G não é prisma-
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
(a) O grafo G e um caminho hamiltoniano
11
(b) Um ciclo hamiltoniano no prisma de G
Figura 2.8: Um ciclo hamiltoniano no prisma de G construı́do a partir de um caminho
hamiltoniano em G.
(a) K2,4
(b) O prisma sobre K2,4 e um ciclo hamiltoniano
Figura 2.9: O grafo K2,4 é prisma-hamiltoniano, mas K2,4 não tem uma 2-árvore.
hamiltoniano, pois se o prisma sobre G tivesse um ciclo hamiltoniano, o ciclo teria que
passar por todas as arestas não tracejadas (veja a Figura 2.10 (b)). No entanto, em
um ciclo hamiltoniano, u2 e u02 não podem ser adjacentes, porque o ciclo obtido seria não
hamiltoniano. Logo u2 , deve ser adjacente a u3 ou u8 . Sem perda de generalidade, assuma
que u2 é adjacente a u3 , então necessariamente u8 é adjacente a u6 e a u08 . Consequentemente, u3 é adjacente ou a u4 ou a u03 . Se u3 é adjacente a u4 , então u03 é adjacente a u02
e a u04 , resultando em um ciclo não hamiltoniano. Por outro lado, se u3 é adjacente a u03 ,
então u4 não pode ser adjacente nem a u04 , pois resultaria em um ciclo não hamiltoniano,
nem a u6 porque já estabelecemos que u6 deve ser adjacente a u8 e a u7 . Portanto, o grafo
não é prisma-hamiltoniano.
Paulraja [23] mostrou que todo grafo bipartido 2-conexo de grau máximo 2 ou 3 é
prisma-hamiltoniano. Nesse mesmo trabalho, ele provou também que todo grafo 3-regular
3-conexo é prisma-hamiltoniano. Mais tarde, Cada et al. [5] apresentaram uma prova mais
simples de que grafos 3-regulares 3-conexos são prisma-hamiltonianos.
Uma outra estrutura útil para mostrar que um grafo é prisma-hamiltoniano foi apresentado em [5, 27]. Um cacto gerador de um grafo G é um subgrafo conexo gerador H
de grau máximo 3 que consiste de ciclos disjuntos em vértices e caminhos disjuntos tal
que, se cada ciclo é substituı́do por um vértice conectado aos caminhos incidentes a ele,
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
(a) G tem um 2 passeio
12
(b) G não é prisma-hamiltoniano
Figura 2.10: Um exemplo de um grafo G que tem um 2-passeio mas não é prismahamiltoniano.
o grafo resultante é uma árvore. Um cacto é chamado de cacto par se todos os ciclos são
pares, ou seja, se o cacto é um grafo bipartido (veja a Figura 2.11).
Figura 2.11: Um cacto par.
Rosenfeld e Barnette [27] e, posteriormente, Čada et al. [5] mostraram que a existência
de um cacto par gerador em um grafo G implica que G é prisma-hamiltoniano.
A busca por ciclos hamiltonianos em prismas sobre grafos tem trazido um novo olhar
sobre muitos problemas relacionados. Uma conjectura de Thomassen [29] de 1986 afirma
que todo grafo linha 4-conexo é hamiltoniano. Kaiser et al. [13] provaram a existência de
ciclos hamiltonianos no prisma destes grafos e também que, para prisma-hamiltonicidade,
é suficiente que o grafo linha seja 2-conexo. Mais tarde, um trabalho de Ozeki [22]
relacionou prisma-hamiltonicidade à uma condição para a soma dos graus de um grafo G,
a exemplo dos conhecidos teoremas de Dirac [6] e de Bondy e Chvátal [2] para a existência
de ciclos hamiltonianos em grafos.
CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
13
O quadrado de um grafo G é o grafo no qual o conjunto de vértices é V (G) e onde
quaisquer dois vértices distintos são adjacentes se e somente se a distância entre eles em
G é de no máximo 2. Um famoso resultado de Fleischner [31] estabelece que o quadrado
de qualquer grafo 2-conexo é hamiltoniano. Kaiser et al. [13] provaram que, para prismahamiltonicidade, é suficiente que o grafo seja somente conexo.
O estudo de prismas sobre grafos motivou também o interesse no produto cartesiano
de um grafo com outros grafos diferentes do grafo completo K2 . Barnette e Rosenfeld [27]
provaram os Teoremas 11 e 12.
Teorema 11 (Barnette e Rosenfeld, 1973 [27]). Se G é um grafo conexo, então GKn é
hamiltoniano para ∆(G) ≤ n.
Teorema 12 (Barnette e Rosenfeld, 1973 [27]). Se G é um grafo conexo, então GC4 é
hamiltoniano para ∆(G) ≤ 4.
Posteriormente, Cada et al. [4] estenderam o Teorema 12 para GCn com ∆(G) ≤ n.
Além disso, dentre outros resultados, os autores também provaram que, se G é um grafo
cúbico sem ponte, então GPt é hamiltoniano, para t ≥ 3.
Utilizando a prova de que grafos 3-regulares 3-conexos são prisma-hamiltonianos [23,
5], Horák et al. [11] provaram que os grafos conhecidos por grafos dos nı́veis intermediários
(“middle-levels graph”, em inglês) são prisma-hamiltonianos. Posteriormente, Bueno e
Horák [3] mostraram que metade dos grafos de uma classe conhecida por grafos ı́mpares
(“odd graph”, em inglês) possuem um subgrafo gerador 3-regular 3-conexo, implicando
assim que estes grafos são prisma-hamiltonianos pelo resultado de [23].
Recentemente, Mesquita et al. [20] mostraram que todos os grafos ı́mpares são prismahamiltonianos ao provar a existência de um cacto par gerador nestes grafos que, de acordo
com [27, 5], é uma condição suficiente para ser prisma-hamiltoniano.
No próximo capı́tulo, estudamos as provas de alguns resultados relacionados existentes
na literatura.
Capı́tulo 3
Classes de Grafos
Prisma-Hamiltonianos
Neste capı́tulo, estudamos algumas provas de prisma-hamiltonicidade para algumas classes
de grafos.
3.1
Grafos bipartidos 2-conexos de grau máximo 2
ou 3
Nesta seção estudamos o resultado de Paulraja [23] que determina que todos os grafos
2-conexos bipartidos com grau máximo 2 ou 3 são prisma-hamiltonianos.
O Teorema 13 foi mostrado por Fleischner [9] e é utilizado na demonstração de
Paulraja [23].
Teorema 13 (Fleischner, 1974 [9]). Seja G um grafo 2-conexo em arestas, e sejam v e
w vértices distintos de G. Então existem subgrafos E e P de G tal que
1. S = E ∪ P é um subgrafo gerador conexo de G;
2. E é uma união de ciclos disjuntos em arestas;
3. P é uma floresta de caminhos;
4. E e P são disjuntos em arestas, e;
5. v ∈ V (E) − V (P ) e w ∈ V (E) − I(P ), onde I(P ) é o conjunto dos vértices internos
de P .
Um subgrafo H de um grafo conexo G é um EP-subgrafo de G (veja a Figura 3.1 (a))
se satisfaz as seguintes condições:
14
CAPÍTULO 3. CLASSES DE GRAFOS PRISMA-HAMILTONIANOS
15
(a) H é um subgrafo gerador conexo de G;
(b) ∆(H) ≤ 4, e;
(c) H = E ∪ P , onde E é uma união de ciclos disjuntos em arestas, P é uma união de
caminhos disjuntos, tal que nenhum vértice de um caminho em P é de grau 4 em H,
e tal que E e P são disjuntos em arestas.
Observe que em um EP-subgrafo H de G, quando duplicamos as arestas dos caminhos
de P , obtemos um multigrafo H 0 com grau máximo 4. Se H 0 admite uma decomposição
em ciclos pares, então dizemos que o EP-subgrafo H de G é um EEP-subgrafo de G. Se H
é um EEP-subgrafo de um grafo G, então H 0 admite uma decomposição em ciclos pares e
é possı́vel colorir as arestas de cada ciclo par com as cores azul e amarelo alternadamente.
Note que duas arestas azuis e duas arestas amarelas devem ser incidentes a cada vértice
de grau 4. Dizemos que um EEP-subgrafo H de G é um SEEP-subgrafo (veja a Figura 3.1
(b)) se H 0 com alguma bicoloração admite uma trilha euleriana que satisfaz a seguinte
regra: qualquer vértice pode ser usado como vértice inicial da trilha euleriana fechada. Se
uma aresta de uma cor é usada para alcançar um vértice v e existe outra aresta da mesma
cor incidente a v, então essa aresta é usada para sair do vértice. Uma trilha euleriana
fechada que satisfaz a regra anterior é chamada de uma AR-trilha.
(a) Um EP-subgrafo H
(b) Um SEEP-subgrafo H 0
Figura 3.1: Exemplos de um EP-subgrafo e de um SEEP-subgrafo.
Teorema 14 (Paulraja, 1993 [23]). Um grafo G é prisma-hamiltoniano se e somente se
G tem um SEEP-subgrafo H.
Demonstração. Denote por G1 e G2 as duas cópias disjuntas de G em GK2 . Denote
as arestas de K2 em GK2 por pilares. Seja C um ciclo hamiltoniano de GK2 . Sejam
e0 , e1 , e2 , · · · , e2t−1 , com t ≥ 1, o conjunto dos pilares que estão em C, na ordem em que
ocorrem em C a partir de uma direção fixa em C. Note que, C − {e0 , e1 , · · · e2t−1 } são 2t
0
caminhos disjuntos P0 , P1 , · · · , Pt−1 em G1 e P00 , P10 , · · · , Pt−1
em G2 . O ciclo C é expressado
0
0
0
como P0 e0 P0 e1 P1 e2 P1 e3 P2 e4 · · · Pt−1 e2t−1 , onde e2k é incidente ao vértice terminal de Pk ,
0
e ao vértice inicial de Pk+1
, para 0 ≤ k ≤ t − 1.
CAPÍTULO 3. CLASSES DE GRAFOS PRISMA-HAMILTONIANOS
16
Alterne as cores das arestas dos caminhos P0 , P1 , · · · , Pt−1 em G1 , com cores B1 e B2
0
e as arestas dos caminhos P00 , P10 , · · · , Pt−1
em G2 com as cores Y1 e Y2 usando a seguinte
regra: colorir as arestas do caminho P0 alternadamente com as cores B1 e B2 . Se a última
aresta de P0 é colorida com B1 (B2 , resp.), então a aresta inicial do caminho P00 é colorida
com Y1 (Y2 , resp.) e a aresta inicial de P1 é colorida com B2 (B1 , resp.) e, assim por
diante.
Construa um multigrafo H0 , onde o conjunto de vértices é V (G), o conjunto de arestas
é o conjunto de arestas dos caminhos P0 , P1 , P2 , · · · , Pt−1 de G1 e o conjunto de arestas
0
de G2 sobre G. Claramente, H0 é conexo e pode ter arestas
dos caminhos P00 , P10 , · · · , Pt−1
múltiplas. O caminho de H0 correspondente ao caminho Pi ou Pi0 , para 0 ≤ i ≤ t − 1,
de G1 ou G2 é denotado por Pi (H0 ) ou Pi0 (H0 ), respectivamente. Colorimos cada aresta
de H0 , com a mesma cor dos caminhos correspondentes em Pi ou Pi0 , 0 ≤ i ≤ t − 1.
Claramente, cada vértice de H0 tem grau 2 ou 4. Em H0 , arestas com as quatro cores
B1 , B2 , Y1 e Y2 são incidentes aos vértices com grau 4, e arestas com cores B1 e Y2 , ou B2
e Y1 são incidentes a cada vértice de grau dois. Sejam H1 e H2 subgrafos de H0 , induzidos
pelas arestas com cores Y1 ou B2 e Y2 ou B1 , respectivamente. Então H1 e H2 são uniões
de ciclos pares disjuntos. Uma vez que H0 = H1 ∪ H2 temos que H0 é uma união de ciclos
pares que são disjuntos em arestas.
Troque a cor das arestas de H0 da seguinte maneira: para e ∈ E(H0 ), atribua a cor
Y se e tem cor Y1 ou Y2 , e a cor B se tem cor B1 ou B2 . Claramente, as arestas dos
caminhos Pi (H0 ) e Pi0 (H0 ), para 0 ≤ i ≤ t − 1, tem cores B e Y , respectivamente. Então
0
(H0 ) é uma AR-trilha de H0 , onde
P0 P00 (H0 )P1 (H0 )P10 (H0 )P2 (H0 )P20 (H0 ) · · · Pt−1 (H0 )Pt−1
0
o vértice terminal de Pi (H0 ) é o vértice inicial de Pi (H0 ) e o vértice terminal de Pi0 (H0 )
é o vértice inicial de Pi+1 (H0 ), para 0 ≤ i ≤ t − 1.
Seja H3 o subgrafo de H0 induzido por suas múltiplas arestas. Como H0 é um grafo
conexo com δ(H0 ) = 2 e ∆(H0 ) ≤ 4, segue que H3 não tem subgrafo 4-regular. Seja
H4 = H0 − E(H3 ). Como H0 é um grafo euleriano, H4 é a união de ciclos disjuntos em
arestas (possivelmente com alguns vértices isolados). Denote os subgrafos P 00 e E 00 de G
como H3 e H4 , respectivamente. Então, P 00 é uma união de caminhos disjuntos e E 00 é
uma união de ciclos disjuntos. Além disso, P 00 e E 00 são disjuntos em arestas. Portanto,
P 00 ∪ E 00 = H é um SEEP-subgrafo de G.
Reciprocamente, se G tem um SEEP-subgrafo H, então obtenha o grafo H 0 de H com
uma bicoloração (usando azul e amarelo) das arestas de H 0 e uma AR-trilha de H 0 . Colora
as arestas de GK2 da seguinte maneira: se existe uma aresta azul ou amarela em H 0 ,
então colora a aresta correspondente em G1 e G2 . Uma vez que H 0 tem uma AR-trilha,
as arestas coloridas de G1 e G2 são uniões de caminhos disjuntos, denotados por P1 e
P2 em G1 e G2 , respectivamente. Como H 0 tem uma AR-trilha, cada vértice terminal
(inicial, resp.) de um caminho em P1 (P2 , resp.) corresponde ao vértice inicial (terminal,
resp.) em G2 de um caminho em P2 (P1 , resp.). Os pilares que conectam os extremos dos
CAPÍTULO 3. CLASSES DE GRAFOS PRISMA-HAMILTONIANOS
17
caminhos de P1 e P2 e os conjuntos de caminhos P1 e P2 fornecem um ciclo hamiltoniano
em GK2 .
Teorema 15 (Paulraja, 1993 [23]). Se G é um grafo bipartido 2-conexo com ∆(G) ≤ 3,
então G é prisma-hamiltoniano.
Demonstração. Seja G um grafo bipartido 2-conexo com grau máximo 2 ou 3. Pelo
Teorema 13, existe um conjunto de ciclos disjuntos C e um conjunto de caminhos disjuntos
P , tal que P e C são disjuntos em arestas, onde H = C ∪ P é um subgrafo gerador conexo
de G. Seja H1 um subgrafo conexo gerador de H tal que os ciclos de H1 são precisamente
os ciclos de C. Note que a contração dos ciclos de H1 em vértices resulta em uma árvore.
Denote a união dos caminhos de H1 como P 00 . Note que E(P 00 ) = E(H1 −∪C1 ∈C E(Ci ))
e que H1 = C ∪ P 00 . Se duplicamos as arestas dos caminhos de P 00 em H1 , obtemos um
grafo euleriano H10 com grau máximo 4. Denote por C 0 a união dos ciclos C com os ciclos
de comprimento dois obtidos ao duplicar as arestas. Note que C 0 é uma decomposição em
ciclos pares de H1 . Além disso, qualquer bicoloração de arestas dos ciclos de C 0 resulta
em uma AR-trilha. Portanto, G tem um SEEP-subgrafo H1 . Pelo Teorema 14, G é
prisma-hamiltoniano.
Corolário 16 (Paulraja, 1993 [23]). Se G tem um subgrafo bipartido gerador 2-conexo H
com ∆(H) ≤ 3, então G é prisma-hamiltoniano.
3.2
Grafos 3-regulares 3-conexos
Paulraja [23] mostrou que todo grafo 3-regular 3-conexo é prisma-hamiltoniano. Mais
tarde, Čada et al. [5] conseguiu uma prova mais simples. Nesta seção estudamos as duas
demonstrações, na ordem que foram apresentadas na literatura.
Teorema 17 (Paulraja, 1993 [23]). Seja B um subgrafo bipartido 2-conexo de um grafo
3-conexo G. Então, G tem um subgrafo bipartido gerador 2-conexo H que contém B.
Teorema 18 (Paulraja, 1993 [23]). Se G é um grafo cúbico 3-conexo, então G é prismahamiltoniano.
Demonstração. Segue do Teorema 17, que G tem um subgrafo bipartido gerador 2-conexo
H. Logo, segue do Teorema 15 que HK2 é hamiltoniano e, portanto, G é prismahamiltoniano.
Čada et al. [5] provam que os grafos 3-regulares 3-conexos são prisma-hamiltonianos
já que eles tem um cacto par gerador.
Lema 19. Um grafo k-conexo G contém um ciclo par para k ≥ 3.
CAPÍTULO 3. CLASSES DE GRAFOS PRISMA-HAMILTONIANOS
18
Demonstração: Sejam u, v ∈ V (G). Como G é k-conexo, segue do Teorema 8 que existem
k (u, v)-caminhos internamente disjuntos P1 , P2 , . . . e Pk . Então existem pelo menos
dois caminhos cujo comprimento tem a mesma paridade. Sem perda de generalidade,
assuma que P1 e P2 têm a mesma paridade e que P1 = (u, p1 , p2 , . . . , pr−1 , pr , v) e P2 =
(u, w1 , w2 , . . . wt−1 , wt , v). Então C = (u, p1 , p2 , . . . , pr−1 , pr , v, wt , wt−1 . . . , w2 , w1 ) é um
ciclo par.
Teorema 20 (Čada et al., 2004 [5]). Um grafo 3-conexo G contém um subgrafo gerador
bipartido 2-conexo.
Demonstração: Segue do Lema 19 que G tem um subgrafo bipartido 2-conexo. Seja H
um subgrafo bipartido 2-conexo maximal de G. Se H não é subgrafo gerador de G; então,
existe um vértice g ∈ V (G) − V (H). Uma vez que H é bipartido; então, os vértices de H
podem ser coloridos de preto e branco. Uma vez que G é 3-conexo, existem 3 caminhos
internamente disjuntos P1 , P2 e P3 de g a um vértice de H. Seja hi o primeiro vértice em
H em cada caminho Pi , 1 ≤ i ≤ 3. Além disso, dois dos vértices de h1 , h2 e h3 tem a
mesma cor. Assuma que os vértices h1 e h2 tem cor branca. Se P1 e P2 tem a mesma
paridade, então g pode ser adicionado a H, contradizendo a maximalidade. Se h3 tem
cor preta então, uma vez que P1 e P2 tem paridades distintas, um deles tem paridade
distinta ao caminho P3 . Ao adicionar esses dois caminhos incrementamos o tamanho de
H. Portanto, H é um subgrafo gerador de G.
Teorema 21 (Petersen, 1891 [24]). Todo grafo 3-regular sem ponte tem um emparelhamento perfeito.
Lema 22 (Čada et al., 2004 [5]). Todo grafo 2-conexo H com ∆(H) ≤ 3 tem um subgrafo
gerador C tal que C é um cacto (não necessariamente par) e suas folhas contém todos os
vértices v com d(v) = 3 em H.
Demonstração. A prova é feita por indução no número de vértices de H. Se |V (H)| ≤ 4,
então H é hamiltoniano. Portanto, C é o ciclo hamiltoniano.
Assuma que H é cúbico. Como H é 2-conexo, pelo Teorema 21 H contém um 1-fator
F . O complemento F̄ = E(G)\F é um 2-fator. Denote por H 0 o grafo obtido ao contrair
cada componente de F̄ em um vértice. Observe que H 0 é conexo. Adicionar as arestas
de qualquer árvore geradora de H 0 em F̄ , resulta em um cacto gerador de H.
Agora, assuma que H não é cúbico. Seja h um vértice de grau 2 em H. Sejam a e b
os vizinhos de h. Se ab ∈ E(H), então, como H é 2-conexo e |V (H)| > 4, temos que a e
b são adjacentes a a0 e b0 , respectivamente, onde a0 6= b0 . Contraia o triângulo ahb em um
vértice c de grau 2 como na Figura 3.2. Claramente, o grafo resultante é 2-conexo. Pela
hipótese de indução, esse grafo tem um cacto gerador C. Se o caminho a0 cb0 pertence a
uma folha, modificamos ao caminho a0 ahbb0 , obtendo assim um cacto gerador em G. Se
CAPÍTULO 3. CLASSES DE GRAFOS PRISMA-HAMILTONIANOS
19
a0 cb0 não é parte de uma folha, então, sem perda de generalidade, assuma que a0 c ∈ E(C).
Modifique o cacto C removendo c e, adicionando o triângulo ahb e a aresta aa0 . Se
b0 c ∈ E(C), então também adicione a aresta bb0 . Como o triângulo é uma folha, o cacto
resultante ainda preserva a propriedade requerida.
Figura 3.2: A contração de um triângulo.
Se ab ∈
/ E(H), então, remova o vértice h e adicione a aresta ab. Pela hipótese de
indução, o grafo resultante tem um cacto gerador C. Se ab ∈ E(C), então, basta substituir
essa aresta pelo caminho ahb. Assuma que ab ∈ E(C). Sem perda de generalidade, assuma
que a tem grau 3 em H então, por hipótese de indução, a pertence a uma folha e podemos
estender C acrescentando a aresta ah. Se ambos a e b tem grau 2 então, como ab ∈
/ E(C),
a tem grau 1 em C. Obtemos um cacto gerador adicionando a aresta ah a C.
A importância do estudo do cacto par em ciclos hamiltonianos é mostrada no seguinte
teorema provado por Rosenfeld e Barnette [27] e, mais tarde, por Čada et al. [5]:
Teorema 23 (Rosenfeld e Barnette, 1973 [27], Čada et al., 2004 [5]). Se um grafo G
contém um cacto par gerador C, então G é prisma-hamiltoniano.
Demonstração. Provamos, por indução no número de vértices de C, que CK2 tem um
ciclo hamiltoniano F tal que:
F contém a aresta xx0 para cada vértice x de grau 2 que pertence a uma folha de C.
(3.1)
Se |V (C)| = 2, então a prova é trivial já que C é um caminho com dois vértices. A
prova é também trivial se C é um ciclo. Assuma que C não é um ciclo. Seja T a árvore
obtida ao contrair cada ciclo Q de C num vértice vQ . Uma vez que T tem pelo menos
dois vértices, escolha um vértice t de grau 1 em T .
Caso 1: Se t ∈ V (C), então, t tem grau um em C e não pertence a nenhuma folha.
Seja u o único vizinho de t em C. Se u pertence a uma folha do cacto C − t então, por
indução, usando a Expressão 3.1, (C − t)K2 tem um ciclo hamiltoniano que contém a
aresta uu0 . Se u não pertence a alguma folha de C − t, então o grau de u em C − t é um e,
portanto, o ciclo hamiltoniano de (C − t)K2 deve conter a aresta uu0 . Em qualquer dos
CAPÍTULO 3. CLASSES DE GRAFOS PRISMA-HAMILTONIANOS
20
casos, substitua a aresta uu0 pelo caminho utt0 u0 obtendo assim um ciclo hamiltoniano em
CK2 e satisfazendo a Expressão 3.1.
Caso 2: Se t = vQ , então, t corresponde a um ciclo Q de C. Uma vez que t tem grau
1 em T seja w o único vértice que tem grau 3 em C. Seja C 0 o grafo obtido ao remover
todos os vértices de Q exceto w de C. Por indução, C 0 K2 tem um ciclo hamiltoniano F 0
que satisfaz a Expressão 3.1 e que, necessariamente, deve conter ww0 já que w tem grau
1 em C 0 . Acrescentando todas as arestas entre Q e Q0 exceto ww0 , obtemos um ciclo em
C que satisfaz a Expressão 3.1.
Agora podemos apresentar a prova alternativa de Čada et al. [5] do Teorema 18.
Demonstração do Teorema 18 (Čada et al.[5]). Pelo Teorema 20, G contém um subgrafo
bipartido 2-conexo gerador H. Ora, G é cúbico, então ∆(H) ≤ 3. Segue do Lema 22 que
H tem um cacto gerador C. Uma vez que H é bipartido, C é par. Finalmente, como C
está contido em G, pelo Teorema 23, G é prisma-hamiltoniano,
Capı́tulo 4
Outros Produtos Cartesianos de
Grafos
Neste capı́tulo, estudamos o problema do ciclo hamiltoniano em produtos cartesianos
de um grafo G com grafos distintos do K2 . Veja na Figura 4.1 o produto cartesiano
C4 C8 . Dado um grafo conexo G, seja G1 = GK2 , G2 = G1 K2 ,. . ., Gq = Gq−1 K2 .
Nosso principal resultado neste capı́tulo é a prova de que Gq é hamiltoniano para todo
q ≥ dlog2 ∆(G)e. Mostramos também que essa prova é equivalente a provar que GQn é
prisma-hamiltoniano para de n = q.
(a) C4 e C8
(b) C4 C8
Figura 4.1: O produto cartesiano entre C4 e C8 .
O Lema 24 mostra que o produto cartesiano de grafos é associativa.
Lema 24. Dados os grafos G, H e I, temos que (GH)I = G(HI).
Demonstração. Sejam os vértices g ∈ V (G), h ∈ V (H) e i ∈ V (I).
((g1 , h1 ), i1 )((g2 , h2 ), i2 ) ∈ E((GH)I) se e somente se
A aresta
[(g1 , h1 ) = (g2 , h2 ) ∧ i1 i2 ∈ E(I)] ou [i1 = i2 ∧ (g1 , h1 )(g2 , h2 ) ∈ E(GH)]
21
CAPÍTULO 4. OUTROS PRODUTOS CARTESIANOS DE GRAFOS
22
⇔ [g1 = g2 ∧ (h1 = h2 ∧ i1 i2 ∈ E(I))] ou [i1 = i2 ∧ [(g1 = g2 ∧ h1 h2 ∈ E(H)) ou
(h1 = h2 ∧ g1 g2 ∈ E(G))]]
⇔ [g1 = g2 ∧ (h1 = h2 ∧ i1 i2 ∈ E(I))] ou [g1 = g2 ∧ (i1 = i2 ∧ h1 h2 ∈ E(H))] ou
[i1 = i2 ∧ h1 = h2 ∧ g1 g2 ∈ E(G)]
⇔ [(g1 = g2 ) ∧ [(h1 = h2 ∧ i1 i2 ∈ E(I)) ou (i1 = i2 ∧ h1 h2 ∈ E(H))]] ou
[(h1 , i1 ) = (h2 , i2 ) ∧ g1 g2 ∈ E(G)]
⇔ [g1 = g2 ∧ (h1 , i1 )(h2 , i2 ) ∈ E(HI)] ou [(h1 , i1 ) = (h2 , i2 ) ∧ g1 g2 ∈ E(G)]
⇔ (g1 , (h1 , i1 ))(g2 , (h2 , i2 )) ∈ E(G(HI)).
Pelo Lema 24, podemos denotar os grafos (GH)I e G(HI) por apenas GHI.
Lema 25. Se H1 é subgrafo de H2 , então GH1 é subgrafo de GH2 .
Demonstração. Como V (H1 ) ⊆ V (H2 ) então V (GH1 ) = V (G) × V (H1 ) ⊆ V (G) ×
V (H2 ) = V (GH2 ). Seja (g1 , h1 )(g2 , h2 ) ∈ E(GH1 ). Então g1 = g2 ∧ h1 h2 ∈ E(H1 ) ⊆
E(H2 ) ou h1 = h2 ∧ g1 g2 ∈ E(G). Então (g1 , h1 )(g2 , h2 ) ∈ E(GH2 ).
Denotamos por K2n o grafo que resulta do produto cartesiano de n grafos K2 , definido
da seguinte maneira:
(
K2 ,
se n = 1;
K2n =
n−1
K2 K2 , se n > 1.
Lema 26. O grafo n-cubo Qn = K2n , para n ≥ 1.
Demonstração. Provamos por indução em n. O caso base n = 1 é trivial, uma vez que
K2 é isomorfo ao grafo Q1 . Suponha que o lema é verdadeiro para n = m, ou seja,
K2m = Qm . Observe que cada vértice no grafo Qm é representado por uma string binária
de m bits (veja o grafo Q2 na Figura 4.2(a)). Para construir Qm+1 , faça duas cópias de
Qm (inclusive dos rótulos dos vértices) e denote por Q0m e Q00m , como na Figura 4.2(b).
Adicione uma aresta entre os vértices correspondentes, obtendo um grafo Q∗m . Observe que
Q∗m = Qm K2 . Modifique os rótulos dos vértices de Q0m acrescentando 0 a esquerda do
rótulo e modifique os rótulos de Q00m acrescentando 1 a esquerda do rótulo (Figura 4.2(c)),
obtendo o grafo Qm+1 . Portanto, Qm+1 é isomorfo ao grafo Qm K2 . Logo, Qm+1 =
Qm K2 = K2m K2 = K2m+1 .
Lema 27. O grafo n-cubo Qn é hamiltoniano, para todo n ≥ 2.
Demonstração. Provamos por indução em n. O caso base n = 2 é trivial uma vez que
Q2 é um ciclo. Assuma que o lema é verdadeiro para n = m. Da demonstração do
CAPÍTULO 4. OUTROS PRODUTOS CARTESIANOS DE GRAFOS
(b) Q02 e Q002
(a) Q2
23
(c) Q∗2 = Q2 K2 = Q3
Figura 4.2: Ilustração da prova do Lema 26.
Lema 26, temos que Qm+1 é isomorfo a Qm K2 . Como Qm é hamiltoniano então Qm K2
é hamiltoniano. Logo, Qm+1 é hamiltoniano.
Definimos a dimensão hamiltoniana de um grafo G, denotado por dimH (G), como
(
dimH (G) =
0,
se G é hamiltoniano;
q
min{q : GK2 é hamiltoniano}, caso contrário.
Note que, se G é desconexo, então G × K2q é desconexo para todo q ∈ N e, portanto
dimH (G) = ∞ ou não existe. Por definição, se G é hamiltoniano então dimH (G) = 0 e,
se G é prisma-hamiltoniano então dimH (G) ≤ 1.
Note que K22 = K2 K2 , K23 = K2 K2 K2 , e assim por diante. Provamos que, para
todo grafo conexo G, temos que GK2n é hamiltoniano para todo n ≥ dlog2 (∆(G))e.
Depois concluı́mos que para todo grafo conexo dimH (G) ≤ dlog2 (∆(G))e.
Teorema 28 (Čada et al., 2009 [4]). Seja G um grafo conexo. Então, GCn é hamiltoniano para n ≥ ∆(G).
Demonstração. A prova é baseada na construção recursiva de um ciclo hamiltoniano em
alguma árvore geradora de G. Seja T uma árvore geradora de G. Seja v0 ∈ V (T ) e T0 um
subgrafo de T tal que V (T0 ) = {v0 }. É fácil notar que o grafo T0 Cn é hamiltoniano.
Repetimos para i = 1, 2, . . . até conseguir um ciclo hamiltoniano em GCn . Seja vi um
vértice em G − V (Ti−1 ) tal que vi é adjacente em T a algum vértice em V (Ti−1 ). seja Gi
o grafo formado apenas pelo vértice vi . Construı́mos um ciclo hamiltoniano em Ti Cn ,
unindo o ciclo Gi Cn com o ciclo hamiltoniano de Ti−1 Cn . Uma vez que cada ciclo
Gi Cn é unido no máximo n vezes aos ciclos hamiltonianos obtidos em cada iteração,
sempre obtemos um ciclo hamiltoniano em T Cn .
Teorema 29. Seja G um grafo conexo. Então, GK2n é hamiltoniano para todo n ≥
dlog2 (∆(G))e.
CAPÍTULO 4. OUTROS PRODUTOS CARTESIANOS DE GRAFOS
24
Demonstração. Seja q = dlog2 (∆(G))e e m = 2q . Mostramos que GK2q é hamiltoniano.
Pelos Lemas 26 e 27, K2q é hamiltoniano. Note que |V (K2q )| = 2q = m. Seja Cm um ciclo
hamiltoniano de K2q . Pelo Teorema 28, GCm é hamiltoniano. Pelo Lema 25, GCm é
subgrafo de GK2q . Uma vez que V (Cm ) = V (K2q ) então V (GCm ) = V (GK2q ). Então
o ciclo hamiltoniano de GCm também é um ciclo hamiltoniano de GK2q . Mostramos,
por indução, que GK2n também é hamiltoniano para n > q. Se GK2n é hamiltoniano,
então é também prisma-hamiltoniano. Logo, (GK2n )K2 é hamiltoniano. Consequentemente, pelo Lema 24, GK2n+1 é hamiltoniano.
Corolário 30. Se G é conexo então dimH (G) ≤ dlog2 ∆(G)e.
Demonstração. Segue diretamente do Teorema 29 e da definição de dimensão hamiltoniana.
Dado um grafo estrela Sn , denotamos o vértice de grau n por vértice central e os
vértices de grau 1 por vértices externos.
A seguir, estudamos a dimensão hamiltoniana dos grafos estrela. Note que, Sn G é
o grafo onde cada vértice de Sn é substituı́do pelo grafo G e, para cada par de vértices
adjacentes em Sn , conectamos os vértices dos G correspondentes. Veja na Figura 4.3 uma
representação do produto entre S4 e K22 .
(a) Representação de S4 K22
(b) S4 K22
Figura 4.3: O produto S4 K22 .
Dado um grafo Sn G, chamamos de G central ao grafo G que é adjacente a n grafos
G e de G externo aos grafos G que são adjacentes apenas ao G central. Agora, podemos
mostrar que dimH (Sn ) é exatamente dlog2 (n)e.
Teorema 31. Se n ≥ 2, para todo grafo estrela Sn , dimH (Sn ) = dlog2 (n)e.
Demonstração. Sejam q = dlog2 ∆(Sn )e = dlog2 (n)e e m = dimH (Sn ). Pelo Corolário 30,
m ≤ q.
CAPÍTULO 4. OUTROS PRODUTOS CARTESIANOS DE GRAFOS
25
Da definição de dimensão hamiltoniana, temos que Sn K2m é hamiltoniano. Seja C
um ciclo hamiltoniano em Sn K2m . Seja r o número de arestas em C que conecta o K2m
central com cada K2m externo. Observe que em C existem pelo menos duas arestas que
conectam o K2m central com cada K2m externo, então r ≥ 2n. Além disso, cada vértice
v do K2m central pode ter no máximo duas arestas em C incidentes em v. Uma vez que
K2m tem 2m vértices, então r ≤ 2 · 2m . Logo, n ≤ 2m e, consequentemente log2 (n) ≤ m e
q = dlog2 (n)e ≤ m. Portanto, q = m.
Pelo Teorema 31, concluı́mos que para grafos conexos em geral não é possı́vel reduzir o
valor de n no Teorema 29. Concluı́mos também que se m < dlog2 (n)e (ou seja, V (K2m ) <
n) então Sn K2m não é hamiltoniano. No teorema a seguir estendemos o resultado anterior
para todo grafo conexo G, com V (G) < n.
Teorema 32. Para n ≥ 3, se G é um grafo conexo com |V (G)| < n então Sn G não é
hamiltoniano.
Demonstração. A prova é por contradição. Suponha que existe um grafo G com |V (G)| <
n tal que Sn G é hamiltoniano. Seja C um ciclo hamiltoniano em Sn G. Seja r o
número de arestas em C que conecta o G central com cada G externo. Como em C
existem pelo menos duas arestas que conectam o G central com cada G externo, então
r ≥ 2n. Também, como cada vértice v do G central pode ter no máximo duas arestas em
C incidentes em v, então r ≤ 2 · |V (G)|. Logo n ≤ |V (G)|, o que contradiz que V (G) < n.
Portanto, Sn G não é hamiltoniano.
Capı́tulo 5
Grafos 4-regulares 4-conexos
Neste capı́tulo estudamos a hamiltonicidade de prismas sobre grafos 4-regulares 4-conexos.
Veja na Figura 5.1 dois exemplos de grafos 4-regulares 4-conexos. Em particular, restringimos o estudo a grafos livres de garras.
(a) O grafo completo K5
(b) O hipercubo Q4
Figura 5.1: Exemplos de grafos 4-regulares 4-conexos.
Em 1971, Nash-Williams [21] conjecturou que:
Conjectura 33 (Nash-Williams, 1971 [21]). Todo grafo 4-regular 4-conexo é hamiltoniano.
O primeiro contra-exemplo apresentado foi o grafo de Meredith [1] (veja a Figura 5.2
(a)) que, entretanto, possui um caminho hamiltoniano (veja a Figura 5.2 (b)). Consequentemente, o grafo de Meredith é prisma-hamiltoniano. McCuaig e Rosenfeld [18]
apresentaram um contra-exemplo para a conjectura de Nash-Williams para grafos bipartidos (veja a Figura 5.3). Como, até agora, todos os contra-exemplos apresentados
para a conjectura de Nash-Williams são grafos prisma-hamiltonianos, Kaiser et al. [13]
conjecturaram que:
26
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
27
Conjectura 34 (Kaiser et al., 2007 [13]). Todo grafo 4-regular 4-conexo é prismahamiltoniano.
(a) O grafo de Meredith
(b) Um caminho hamiltoniano no grafo de
Meredith
Figura 5.2: Um caminho hamiltoniano no grafo de Meredith.
Figura 5.3: Um grafo 4-regular 4-conexo bipartido não hamiltoniano.
Observe que o Teorema 20 pode ser estendido a grafos k-conexos, com k ≥ 3. Portanto,
se G é 4-regular 4-conexo, então G tem um subgrafo gerador bipartido 2-conexo de grau
máximo 4. Pelo Teorema 15, se G contém um subgrafo gerador bipartido 2-conexo com
grau máximo 2 ou 3, então G é prisma-hamiltoniano. Assim, para provar a Conjectura 34,
uma possı́vel abordagem é tentar limitar o grau máximo do subgrafo gerador bipartido
2-conexo a 2 ou 3, quando considerando grafos 4-regulares 4-conexos.
Observe que os grafos 4-regulares tem um 2-passeio.
Proposição 35. Todo grafo 4-regular conexo tem um 2-passeio.
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
28
Demonstração. Seja G um grafo 4-regular. Pelo Teorema 5, G tem uma trilha euleriana
fechada que passa exatamente duas vezes por cada vértice. Logo, G tem um 2-passeio.
5.1
Grafos 4-regulares 4-conexos livres de garras
Nesta seção, estudamos os grafos 4-regulares 4-conexos livres de garras. Uma das propriedades dessa classe de grafos é não ser bipartido.
Sabemos que todo grafo linha é livre de garra. Portanto, a classe de grafos livres de
garras é uma generalização da classe dos grafos linha. Duas conjecturas relacionadas à
hamiltonicidade de grafos livres de garras foram propostas:
Conjectura 36 (Matthews e Summer, 1984 [17]). Todo grafo 4-conexo livre de garras é
hamiltoniano.
Conjectura 37 (Plummer, 1993 [25]). Todo grafo 4-regular 4-conexo livre de garras é
hamiltoniano.
Ryjáček [28] mostrou que a Conjectura 36 é equivalente a conjectura de Thomassen [29]
que afirma que todo grafo linha 4-conexo é hamiltoniano. O autor também demostrou
que todo grafo 7-conexo livre de garras é hamiltoniano. Mais tarde, Kaiser e Vrána [14]
provaram que os grafos 5-conexos livres de garras com grau mı́nimo de pelo menos 6 são
hamiltonianos.
Denotamos a classe dos grafos 4-regulares 4-conexos livres de garras por G. Como
veremos a seguir, esta classe pode ser dividida em três conjuntos:
• G0 : grafos que contém um grafo completo K4 .
• G1 : grafos que, para dois ciclos disjuntos C1 = u1 u2 . . . uq e C2 = v1 v2 . . . vq com
q ≥ 3, cada ui está conectado a cada vi−1 e vi , onde os subscritos são tomados em
módulo q (veja a Figura 5.4).
• G2 : grafos nos quais todo vértice encontra-se em exatamente dois triângulos (veja
Figura 5.5).
O Teorema 38 prova uma propriedade dos grafos em G0 .
Teorema 38 (Plummer, 1995 [26]). Se G é um grafo livre de garras 4-regular 4-conexo
e contém um K4 então G = K5 ou o conjunto de vértices V (G) pode ser particionado em
conjuntos disjuntos de quatro vértices tal que cada conjunto de quatro vértices induz um
K4 em G.
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
(a)
29
(b)
Figura 5.4: Exemplos de dois grafos em G1 .
(a) L(K3,3 )
(b) L(C5 K2 )
Figura 5.5: Exemplos de dois grafos em G2 .
Plummer [26] mostrou que:
Teorema 39 (Plummer, 1995 [26]). Um grafo G pertence a classe G2 se e somente se
G = L(H) onde H é um grafo cúbico 3-conexo ciclicamente 4-conexo, ou H = K3,3 .
Plummer [26] provou que a classe dos grafos 4-regulares 4-conexos livres de garras
pode ser particionado nos três conjuntos G0 , G1 e G2 :
Teorema 40 (Plummer, 1995 [26]). A classe de todos os grafos 4-regulares 4-conexos
livres de garras é G0 ∪ G1 ∪ G2 , onde G0 , G1 e G2 são dois a dois disjuntos.
Agora apresentamos o resultado principal desta seção. Provamos que os grafos em G0
e G1 são hamiltonianos e que os grafos em G2 são prisma-hamiltonianos.
Denotamos por G o conjunto dos grafos formados ao conectar r grafos completos K4
com um emparelhamento perfeito, para r ≥ 2. Note que os grafos de G são livres de garras
e são 4-regulares mas não necessariamente 4-conexos. Note também que G0 \K5 ⊂ G.
Teorema 41. Todo grafo em G é hamiltoniano.
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
30
Demonstração. Seja G ∈ G. Para r ≥ 2, denote as r cópias induzidas de K4 em G por
K4 (1), K4 (2), . . . , K4 (r) e, para 1 ≤ u ≤ r, denote os vértices de K4 (u) por u1 , u2 , u3 e u4 .
Observe que há um emparelhamento perfeito em G que conecta todas as cópias induzidas
de K4 ; as arestas deste emparelhamento perfeito são chamadas arestas externas.
Provamos por indução em r, o número de cópias de K4 . O caso base é r = 2 (veja a
Figura 5.6). Claramente, G é hamiltoniano uma vez que qualquer ordem dos vértices em
K4 (i) é um ciclo hamiltoniano para i = 1, 2.
Figura 5.6: Grafo em G com r = 2.
Agora, suponha que a hipótese é válida para r ≥ 2 e seja m = r + 1. Seja G0 um
grafo construı́do a partir de G, tal que G0 tem r cópias induzidas de K4 . Como G0 é
hamiltoniano por hipótese, seja C 0 um ciclo hamiltoniano em G0 . Note que somente no
caso base, K4 (m) tem todas as arestas externas para um mesmo K4 (u), onde u 6= m. Se
K4 (m) tem três arestas externas para K4 (u) então G não é 4-conexo. Considere três casos
para construir um ciclo hamiltoniano em G:
Caso 1: K4 (m) tem duas arestas externas para K4 (u) e duas arestas externas
para K4 (v). Uma vez que K4 é simétrico, denote as arestas externas de K4 (m) por
m1 u1 , m2 u2 , m3 v1 e m4 v2 , sem perda de generalidade. Construa um grafo G0 com r cópias
de K4 conectando u1 a v1 e u2 a v2 (veja a Figura 5.7). Para construir um ciclo hamiltoniano C em G, considere três subcasos:
(i) Se ambas as arestas u1 v1 e u2 v2 estão em C 0 , então substitua em C 0 a aresta u1 v1
pelo caminho (u1 , m1 , m3 , v1 ) e a aresta u2 v2 pelo caminho (u2 , m2 , m4 , v2 ) (veja a
Figura 5.8(a)).
(ii) Se somente u1 v1 ∈ C 0 , então substitua em C 0 a aresta u1 v1 pelo caminho
(u1 , m1 , m2 , m4 , m3 , v1 ). O caso é análogo se somente u2 v2 ∈ C 0 (Figura 5.8(b)).
(iii) Se nem u1 v1 nem u2 v2 estão em C 0 , então C 0 contém arestas externas com extremos
em u3 , u4 , v3 e v4 . Portanto, C 0 contém as arestas u1 u2 e v1 v2 . Então substitua
em C 0 a aresta u1 u2 pelo caminho (u1 , m1 , m2 , u2 ) e a aresta v1 v2 pelo caminho
(v1 , m3 , m4 , v2 ) (Figura 5.8(c)).
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
31
Figura 5.7: Remoção de K4 (m) no Caso 1.
(a)
(b)
(c)
Figura 5.8: Construção de um ciclo hamiltoniano para o Caso 1 do Teorema 41
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
32
Caso 2: K4 (m) tem duas arestas externas a K4 (u), uma aresta externa a K4 (v) e
uma aresta externa a K4 (w). Sem perda de generalidade, suponha que as arestas externas
de K4 (m) são m1 u1 , m2 u2 , m3 v1 e m4 w1 . Construa um grafo G0 com r cópias de K4
conectando u1 a v1 e u2 a w1 (Figura 5.9). Para obter um ciclo hamiltoniano C, considere
três subcasos:
(i) Se ambas as arestas u1 v1 e u2 w1 estão em C 0 , então substitua em C 0 a aresta
u1 v1 pelo caminho (u1 , m1 , m3 , v1 ) e a aresta u2 w1 pelo caminho (u2 , m2 , m4 , w1 )
(Figura 5.10(a)).
(ii) Se somente u1 v1 ∈ C 0 , então substitua em C 0 a aresta u1 v1 pelo caminho
(u1 , m1 , m2 , m4 , m3 , v1 ). O caso é análogo se somente u2 w1 ∈ C 0 (Figura 5.10(b)).
(iii) Se nem u1 v1 nem u2 w1 estão em C 0 , então C 0 contém arestas externas com extremos
em u3 e u4 . Portanto, C 0 contém a aresta u1 u2 . Substitua em C 0 a aresta u1 u2 pelo
caminho (u1 , m1 , m3 , m4 , m2 , u2 ) (Figura 5.10(c)).
Figura 5.9: Construção de G0 para o caso 2 do Teorema 41.
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
(a)
33
(b)
(c)
Figura 5.10: Construção de um ciclo hamiltoniano para o Caso 2 do Teorema 41.
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
34
Caso 3: K4 (m) tem uma aresta externa a K4 (u), K4 (v), K4 (w) e K4 (t), para 1 ≤ u 6=
v 6= w 6= t ≤ r. Sem perda de generalidade, suponha que as arestas externas de K4 (m)
são m1 v2 , m2 u3 , m3 w3 e m4 t2 . Também, suponha que o grafo 4-regular G0 com r cópias
de K4 conectando u3 a v2 e w3 a t2 é conexo. Uma vez que, se G0 não é conexo, as duas
componente de G0 são 2-conexo. Então, o grafo 4-regular formado ao conectar u3 a t2 e
w3 a v2 é conexo 4-regular. Sendo a prova análoga ao caso quando G0 é conexo.
Figura 5.11: Construção de G0 para o Caso 3 do Teorema 41.
Para construir um ciclo hamiltoniano C, considere três subcasos:
(i) Se ambas as arestas v2 u3 e t2 w3 estão em C 0 , então substitua em C 0 a aresta
v2 u3 pelo caminho (v2 , m1 , m2 , u3 ) e a aresta t2 w3 pelo caminho (t2 , m4 , m3 , w3 )
(Figura 5.12(a)).
(ii) Se somente v2 u3 ∈ C 0 , então substitua em C 0 a aresta v2 u3 pelo caminho
(v2 , m1 , m3 , m4 , m2 , u3 ). O caso é análogo se somente t2 w3 ∈ C 0 (Figura 5.12(b)).
(iii) Se nem v2 u3 nem t2 w3 estão em C 0 , então mostramos que existe outro ciclo hamiltoniano C 00 em G0 que contém uma ou ambas as arestas v2 u3 e t2 w3 , tal que nós
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
35
podemos proceder como em (i) ou (ii). Para 1 ≤ j ≤ r, seja K o conjunto
dos subgrafos K4 (j) tal que todos os vértices de K4 (j) são consecutivos em C 0 .
Note que K4 (u), K4 (v), K4 (w) e K4 (t) estão em K. Sem perda de generalidade,
suponha que os vértices de cada K4 (i) ∈ K aparecem em C 0 em ordem crescente dos
ı́ndices dos vértices. Considere K4 (u) e K4 (v). A análises para K4 (w) e K4 (t)
é análoga. Suponha C 0 = (i1 , i2 , i3 , i4 , . . . , u1 , u2 , u3 , u4 , . . . , v1 , v2 , v3 , v4 , . . .). Se
u2 v3 ∈ E(G0 ), então C 00 = (i1 , i2 , i3 , i4 , . . . , u1 , u2 , v3 , v2 , u3 , u4 , . . . , v1 , v4 , . . .). Se
u2 v3 ∈
/ E(G0 ), então deve existir um subgrafo K4 (z) ∈ K\{K4 (u), K4 (v)} tal que
v3 z2 ∈ E(G0 ) (ou v3 z3 ∈ E(G0 ) que é o mesmo, uma vez que K4 é simétrico).
Suponha C 0 = (i1 , i2 , i3 , i4 , . . . , u1 , u2 , u3 , u4 , . . . , v1 , v2 , v3 , v4 , . . . , z1 , z2 , z3 , z4 , . . .). A
ordem dos subgrafos de K em C 0 não muda a prova. Se z3 u2 ∈ E(G0 ), então C 00 =
(i1 , i2 , i3 , i4 , . . . , u1 , u2 , z3 , z2 , v3 , v2 , u3 , u4 , . . . , v1 , v4 , . . . , z1 , z4 , . . .). Se z3 u2 ∈
/ E(G0 )
então, como com K4 (v), z3 tem que ser adjacente a algum x2 ∈ K4 (x) ∈ K e assim
por diante. Como K é um conjunto finito, existe um K4 (y) ∈ K tal que y3 u2 ∈ E(G0 )
(Figura 5.13).
(a)
(b)
Figura 5.13: Construção de um ciclo hamiltoniano para o Caso 3(iii) do Teorema 41.
Caso 4: K4 (m) tem três arestas externas a K4 (u) e uma aresta externa a K4 (v). Sem
perda de generalidade, assuma que as arestas externas de K4 (m) são m1 u1 , m2 u2 , m3 u3 e
m4 v1 . Para construir um grafo G0 , considere os seguintes subcasos:
(i) Se K4 (u) é adjacente a K4 (v), então suponha que u4 v2 ∈ E(G). Se K4 (v) é adjacente
a uma outra cópia de K4 (veja a Figura 5.14(a)), então o caso é idêntico ao Caso
2(i). Se K4 (v) é adjacente a outras duas cópias de K4 (veja a Figura 5.14(b)) então
proceda como no Caso 3(i).
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
(a)
36
(b)
Figura 5.12: Construção de um ciclo hamiltoniano para o Caso 3 do Teorema 41.
(ii) Se K4 (u) é adjacente a uma cópia K4 (w), onde w 6= v então, sem perda de generalidade, suponha que u4 é adjacente a w1 . Construa um grafo de r − 1 cópias de K4
conectando os vértices v1 e w1 (veja a Figura 5.15(a)). Se v1 w1 ∈ C 0 , então substitua
a aresta v1 w1 pelo caminho (v1 , m4 , m1 , m2 , m3 , u3 , u2 , u1 , u4 , w1 ) (Figura 5.15(b)).
Se v1 w1 ∈
/ C 0 , foi mostrado no Caso 3(iii) que existe um ciclo hamiltoniano que
contém a aresta v1 w1 .
Agora, apresentamos outra prova do teorema anterior:
Demonstração alternativa do Teorema 41. Seja G ∈ G. Denote as r ≥ 2 cópias de K4
por K4 (1), K4 (2), . . . , K4 (r). Contraia cada cópia K4 (i) em um vértice vi . O multigrafo
resultante M é 4-regular e, pelo Teorema 5, tem uma trilha euleriana fechada. Essa trilha
no multigrafo M corresponde a um ciclo hamiltoniano em G.
Teorema 42. Todo grafo G em G0 ∪ G1 é hamiltoniano.
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
(a)
37
(b)
Figura 5.14: Análise do Caso 4(i) do Teorema 41.
Demonstração. Se G ∈ G0 , pelo
Como K5 é hamiltoniano e pelo
G1 . Sejam C1 = (u1 , u2 . . . , uk )
(u1 , v1 , u2 , v2 , u3 , v3 , . . . , uk , vk ) é
Teorema 38 temos que ou G = K5 ou G ∈ G0 \K5 ⊂ G.
Teorema 41, concluı́mos que G é hamiltoniano. Se G ∈
e C2 = (v1 , v2 , . . . , vk ) os ciclos que formam G. Então
um ciclo hamiltoniano.
Para provar que G2 é prisma-hamiltoniano, necessitamos de uma definição adicional.
Definimos a conectividade cı́clica de um grafo G como a menor cardinalidade sobre todos
os cortes de arestas F de G tal que pelo menos dois componentes de G − F contêm
ciclo. Denotamos a conectividade cı́clica de G por cλ(G). Dizemos que G é ciclicamente
k-conexo se k ≤ cλ(G).
Teorema 43 (Plummer, 1995 [26]). Um grafo G pertence a G2 se e somente se G = L(H)
onde H é um grafo cúbico 3-conexo ciclicamente 4-conexo, ou H = K3,3 .
Kaiser et al. [13] mostraram que:
Teorema 44 (Kaiser et al., 2007 [13]). O prisma sobre o grafo linha de qualquer grafo
sem ponte é hamiltoniano.
Corolário 45. Todo grafo G em G2 é prisma-hamiltoniano.
Demonstração. Pelo Teorema 43, G = L(K3,3 ) ou G = L(H) onde H é 3-conexo. É fácil
ver que L(K3,3 ) (Figura 5.5(a)) é hamiltoniano. Caso contrário, se G 6= L(K3,3 ), temos
que H não tem ponte, então G é prisma-hamiltoniano, pelo Teorema 44.
Corolário 46. Todo grafo livre de garras 4-regular 4-conexo G é prisma- hamiltoniano.
Demonstração. Segue dos Teoremas 40 e 42 e do Corolário 45.
CAPÍTULO 5. GRAFOS 4-REGULARES 4-CONEXOS
(a)
38
(b)
Figura 5.15: Construção de G0 para o Caso 4(ii) do Teorema 41.
Capı́tulo 6
Conclusões
No estudo do problema de ciclos hamiltonianos, determinar um ciclo hamiltoniano no
produto cartesiano de grafos tem se mostrado uma relaxação interessante do problema.
Neste trabalho, estudamos a conjectura de Kaiser et al. [13] que afirma que todo grafo
4-regular 4-conexo é prisma-hamiltoniano. Provamos essa conjectura para grafos livres
de garras. Além disso, para uma das subclasses de grafos livres de garras, provamos
um resultado mais forte ao mostrar a hamiltonicidade dessa subclasse. Esse resultado
corrobora a conjectura de Plummer [25] que afirma que grafos 4-regulares 4-conexos livres
de garras são hamiltonianos. Dessa forma, para provar a conjectura de Plummer [25],
resta provar a hamiltonicidade da subclasse G2 .
Finalmente, provamos também que, se G é conexo, então Gq é hamiltoniano para todo
q ≥ dlog2 ∆(G)e, o que implica que a dimensão hamiltoniana de G é menor ou igual a
dlog2 ∆(G)e.
Resultados preliminares desta dissertação foram apresentadas na Escola LatinoIberoamericana de Verão em Pesquisa Operacional, realizada em Areia-PB em
fevereiro/2014. Um resumo estendido com parte dos resultados será apresentado no 9th International Colloquium on Graph Theory and Combinatorics (ICGT 2014) em Grenoble,
França em julho/2014.
39
Referências Bibliográficas
[1] J. A. Bondy e U. S. R. Murty. Graph theory. Graduate texts in mathematics. Springer,
New York, London, 2007.
[2] J.A. Bondy e V. Chvatal. A method in graph theory. Discrete Mathematics, 15(2):111
– 135, 1976.
[3] L. R. Bueno e P. Horák. On hamiltonian cycles in the prism over the odd graphs.
Journal of Graph Theory, 68(3):177–188, 2011.
[4] R. Čada, E. Flandrin e H. Li. Hamiltonicity and pancyclicity of cartesian products
of graphs. Discrete Mathematics, 309(22):6337 – 6343, 2009.
[5] R. Čada, T. Kaiser, M. Rosenfeld e Z. Ryjáček. Hamiltonian decompositions of
prisms over cubic graphs. Discrete Mathematics, 286:45–56, 2004.
[6] G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 2:69–81, 1952.
[7] G. A. Dirac. In abstrakten graphen vorhandene vollständige 4-graphen und ihre
unterteilungen. Mathematische Nachrichten, 22(1-2):61–85, 1960.
[8] L. Euler. Solutio problematis ad geometriam situs pertinentis.
academiae scientiarum Petropolitanae, 8:128–140, 1736.
Commentarii
[9] H. Fleischner. On spanning subgraphs of a connected bridgeless graph and their
application to DT-graphs. Journal of Combinatorial Theory, Series B, 16(1):17 – 28,
1974.
[10] M. R. Garey e D. S. Johnson. Computers and Intractability, A Guide to the Theory
of NP-Completeness. W.H. Freeman and Company, New York, 1979.
[11] P. Horák, T. Kaiser, M. Rosenfeld e Z. Ryjáček. The prism over the middle-levels
graph is hamiltonian. Order, 22(1):73–81, 2005.
[12] B. Jackson e N. C. Wormald. k-walks of graphs. Australasian Journal of Combinatorics, 2:135–146, 1990.
40
REFERÊNCIAS BIBLIOGRÁFICAS
41
[13] T. Kaiser, Z. Ryjáček, D. Král, M. Rosenfeld e H. J. Voss. Hamilton cycles in prisms.
Journal of Graph Theory, 56:249–269, 2007.
[14] T. Kaiser e P. Vrána. Hamilton cycles in 5-connected line graphs. European Journal
of Combinatorics, 33(5):924 – 947, 2012. EuroComb ’09.
[15] R. M. Karp. Reducibility among combinatorial problems. In R.E. Miller and J.W.
Thatcher, editors, Complexity of Computer Computations, pages 85–103, New York,
1972. Plenum Press.
[16] D. König. Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 77(4):453–465, 1916.
[17] M. M. Matthews e D. P. Sumner. Hamiltonian results in K1,3 -free graphs. Journal
of Graph Theory, 8(1):139–146, 1984.
[18] W.D. McCuaig e M. Rosenfeld. Cyclability of r-regular r-connected graphs. Bulletin
of the Australian Mathematical Society, 29(1):1–11, 1984.
[19] K. Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10(1):96–
115, 1927.
[20] F. C. Mesquita, L. R. Bueno e R. A. Hausen. Odd graphs are prism-hamiltonian
and have a long cycle. In 11th Latin American Theoretical Informatics Symposium
(LATIN’14), Montevideo-Uruguay, volume 8392, pages 379–390, 2014.
[21] C.St.J.A. Nash-Williams. Hamiltonian arcs and circuits. In M. Capobianco, J.B.
Frechen, and M. Krolik, editors, Recent Trends in Graph Theory, volume 186 of
Lecture Notes in Mathematics, pages 197–210. Springer Berlin Heidelberg, 1971.
[22] K. Ozeki. A degree sum condition for graphs to be prism hamiltonian. Discrete
Mathematics, 309(13):4266 – 4269, 2009.
[23] P. Paulraja. A characterization of hamiltonian prisms. Journal of Graph Theory,
17:161–171, 1993.
[24] J. Petersen. Die theorie der regulären graphs. Acta Mathematica, 15(1):193–220,
1891.
[25] M. D. Plummer. A note on hamilton cycles in claw-free graphs. Congressus Numerantium, pages 113–113, 1993.
[26] M.D. Plummer. 2-extendability in two classes of claw-free graphs. In Y. Alavi and
A.J. Schwenk, editors, Graph Theory, Combinatorics, and Algorithms, volume 2,
pages 905–922. Wiley, New York, 1995.
REFERÊNCIAS BIBLIOGRÁFICAS
42
[27] M. Rosenfeld e D. Barnette. Hamiltonian circuits in certain prisms. Discrete Mathematics, 5(4):389 – 394, 1973.
[28] Z. Ryjáček. On a closure concept in claw-free graphs. Journal of Combinatorial
Theory, Series B, 70(2):217 – 224, 1997.
[29] C. Thomassen. Reflections on graph theory. Journal of Graph Theory, 10:309–324,
1986.
[30] H. Whitney. Congruent graphs and the connectivity of graphs. American Journal of
Mathematics, 54:150–168, 1932.
[31] H. Whitney. The square of every two-connected graph is hamiltonian. Journal of
Combinatorial Theory B, 16:26–34, 1974.
Índice Remissivo
k-árvore, 9
k-fator, 9
k-passeio, 9
k-subconjunto, 3
n-cubo, 8
árvore, 6
geradora, 7
AR-trilha, 15
aresta incidente, 3
automorfismo, 4
cacto gerador, 11
cacto par, 12
caminho, 6
caminhos internamente disjuntos, 7
hamiltoniano, 6
ciclo, 6
hamiltoniano, 6
cobertura de vértices por ciclos, 8
comprimento, 5
conectividade, 7
conectividade cı́clica, 37
conectividade em arestas, 7
corte de arestas, 7
k-corte de arestas, 7
corte de vértices, 7
k-corte de vértices, 7
dimensão hamiltoniana, 23
distância entre vértices, 6
EEP-subgrafo, 15
emparelhamento, 9
máximo, 9
perfeito, 9
EP-subgrafo, 14
estrela, 5
garra, 5
grafo, 3
k-regular, 5
não trivial, 3
aresta-transitivo, 4
bipartido, 5
completo, 5
cúbico, 5
ciclicamente k conexo, 37
completo, 5
conexo, 6
k-conexo, 7
k-conexo em arestas, 7
desconexo, 6
euleriano, 6
linha, 8
livre de garra, 5
produto cartesiano, 8
simétrico, 4
simples, 3
trivial, 3
união, 3
vértice-transitivo, 4
grafos
k-fatorável, 9
isomorfos, 4
grafos idênticos, 4
grau, 4
máximo, 5
43
ÍNDICE REMISSIVO
mı́nimo, 5
isomorfismo, 4
passeio, 5
aberto, 6
extremos do passeio, 6
fechado, 6
vértices internos, 6
ponte, 7
ponto de articulação, 7
prisma
prisma-hamiltoniano, 10
prisma , 10
quadrado de um grafo, 13
SEEP-subgrafo, 15
subgrafo, 4
gerador, 4
induzido, 4
máximo, 4
maximal, 4
próprio, 4
trilha, 6
euleriana, 6
fechada, 6
vértice central, 24
vértice externo, 24
vértices adjacentes, 3
vizinhança, 4
44