CONJECTURA DE HOFFMANN-OSTENHOF
Resumo
A 3-Decomposition Conjecture (3DC) estabelece que cada grafo conexo cúbico pode ser decomposto em uma árvore geradora, um subgrafo 2-regular e um emparelhamento. Estudamos o artigo "Decomposing planar cubic graphs" de Arthur Hoffmann-Ostenhof, Tomás Kaiser e Kenta Ozeki o qual mostra que esta conjectura é verdadeira para a classes dos grafos cúbicos planares conexos. Todos os grafos considerados são finitos e sem laços. Uma decomposição de um grafo G é um conjunto de subgrafos cujos conjuntos de arestas particionam o conjunto das arestas de G. Qualquer um desses subgrafos pode ser o grafo vazio - isto é, um grafo cujo conjuto de vértices é vazio - a menos que seja excluídos por restrições adicionais (tais como ser uma árvore geradora). Consideramos emparelhamentos em decomposições como subgrafos 1-regular. O subgrafo 2-regular, na 3DC pode ser vazio, enquanto que o emparelhamento não. A 3DC foi provada para grafos cúbicos planares e planares-projetivos 3-conexo em arestas em "K. Ozeki, D. Ye, Decomposing plane cubic graphs, European J. Combin. 52 (2016), 40–46". Também é conhecido que essa conjectura é válida para grafos cúbicos Hamiltonianos. Chamamos um ciclo C em um grafo conexo de separador se G − E(C) é desconexo. Foi mostrado que 3DC é equivalente a seguinte conjecture, chamada 2-Decomposition Conjecture (2DC). 2DC: Seja G um grafo conexo com vértices de grau dois e três, apenas, tal que todo ciclo de G é separador. Então G pode ser decomposto em uma árvore geradora e um emparelhamento não-vazio. O objetivo da bolsa foi estudar e entender o artigo visando resolver a conjectura para o caso geral.
Publicado
2019-01-14
Edição
Seção
XXXVII Encontro de Iniciação Científica
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
a. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License que permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
b. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.
