Made available in DSpace on 2014-06-12T18:28:59Z (GMT). No. of bitstreams: 2
arquivo648_1.pdf: 827994 bytes, checksum: 5bd18eefcbed6a0d647716cdc47627b9 (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2011 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/7100 |
| Date | 31 January 2011 |
| Creators | Paulo Costalonga, João |
| Contributors | José Machado Soares Lemos, Manoel |
| Publisher | Universidade Federal de Pernambuco |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds