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 | Size | Format | |
---|---|---|---|---|
arquivo648_1.pdf | 808.59 kB | Adobe PDF | View/Open |
This item is protected by original copyright |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.