Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.ufpe.br/handle/123456789/7100
Title: Cocircuitos não-separadores que evitam um elemento e graficidade em matroides binárias
Authors: Paulo Costalonga, João
Keywords: Matroides;Teoria dos grafos
Issue Date: 31-Jan-2011
Publisher: Universidade Federal de Pernambuco
Citation: Paulo Costalonga, João; José Machado Soares Lemos, Manoel. Cocircuitos não-separadores que evitam um elemento e graficidade em matroides binárias. 2011. Tese (Doutorado). Programa de Pós-Graduação em Matemática, Universidade Federal de Pernambuco, Recife, 2011.
Abstract: Bixby e Cunningham relacionaram graficidade de matroides binárias 3-conexas e cocircuitos não separadores, generalizando um critério de planaridade de grafos 3-conexos de Tutte. Lemos estudou o conjunto de cocircuitos não-separadores que evita um elemento de uma matroide binária 3-conexa e conseguiu outra caracterização: M é gráfica se e só se cada elemento de M evita exatamente r (M)¡1 cocircuitos não separadores. Aqui estudamos o conjunto Y (M), dessas obstruções para graficidade, formado pelos elementos de M que evitam no mínimo r (M) cocircuitos não-separadores. Mostramos que, numa matroide binária 3-conexa existem 3 circuitos contidos em Y (M), cada qual não contido na união dos outros dois. Isso implica numa generalização do resultado de Lemos. No caso em que M não possui menor M¤(K000 3,3) ou M não é regular, conseguimos resultado muito melhor: jE(M)¡Y (M)j · 1. A demonstração desses resultados se baseia numa extensão de alguns resultados de Whittle a respeito demenores de matroide 3-conexas, que também são desenvolvido aqui: Seja M uma matroide binária e 3-conexa com um menor 3-conexo N. Suponha que r (M) ¸ r (N)Å3. Então existe um 3-coindependente I ¤ de M tal que co(M\e) é 3-conexa com menor isomorfo a N para todo e 2 I ¤. No mesmo capítulo desse teorema mostramos ainda uma versão para grafos que, porém, não se extende para matroides binárias
URI: https://repositorio.ufpe.br/handle/123456789/7100
Appears in Collections:Teses de Doutorado - Matemática

Files in This Item:
File Description SizeFormat 
arquivo648_1.pdf808.59 kBAdobe PDFView/Open


This item is protected by original copyright



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.