19jul2022
09:00 Defesa de Doutorado Auditório do IC3
Tema
Path partition problems in digraphs
Aluno
Lucas Ismaily Bezerra Freitas
Orientador / Docente
Orlando Lee
Breve resumo
Seja D um digrafo. Um subconjunto S de V(D) é um conjunto estável se todo par de vértices em S é não adjacente em D. Uma coleção de caminhos disjuntos P de D é uma partição de caminhos de D, se todo vértice em V(D) pertence a exatamente um caminho de P. Dizemos que um conjunto estável S e uma partição de caminhos P são ortogonais se todo caminho de P contém exatamente um vértice de S. Um digrafo D satisfaz a α-propriedade se para todo conjunto estável máximo S de D, existe uma partição de caminhos P tal que S e P são ortogonais. Um digrafo D é α-diperfeito se todo subdigrafo induzido de D satisfaz a α-propriedade. Em 1982, Berge propôs uma caracterização para digrafos α-diperfeitos em termos da proibição de circuitos ímpares anti-orientados induzidos. Em 2018, Sambinelli, Silva e Lee propuseram uma conjectura semelhante. Um digrafo D satisfaz a Begin-End-propriedade, ou BE-propriedade, se para todo conjunto estável máximo S de D, existe uma partição de caminhos P tal que (i) S e P são ortogonais e (ii) para todo caminho Q em P, o início ou o fim de Q pertence a S. Um digrafo D é BE-diperfeito se todo subdigrafo induzido de D satisfaz a BE-propriedade. Sambinelli, Silva e Lee propuseram uma caracterização para digrafos BE-diperfeitos em termos da proibição de circuitos ímpares bloqueantes induzidos. Nesta tese, verificamos ambas as conjecturas para digrafos arco-local in-semicompletos, arco-local out-semicompletos, arco-local semicompletos, 3-anti-circulantes, 3-anti-digon-circulantes e quase-transitivos. Além disso, provamos alguns resultados parciais para digrafos 3-quase-transitivos, 4-transitivos, k-semi-simétricos e digrafos com estabilidade igual a dois. Também demonstramos alguns resultados estruturais para digrafos α-diperfeitos e BE-diperfeitos. Além disso, fornecemos uma caracterização para digrafos arbitrários arco-local (out) in-semicompletos e para arbitrários arco-local semicompletos. Mostramos que a estrutura desses digrafos é semelhante a digrafos diperfeitos. Ademais, fornecemos alguns resultados estruturais para digrafos 3-anti-digon-circulantes. Demonstramos que a estrutura desses digrafos é semelhante a digrafos completos e bipartidos completos.
Banca examinadora
Titulares:
| Orlando Lee | IC/UNICAMP |
| Ana Shirley Ferreira da Silva | MAT/UFC |
| Simone Dantas de Souza | IME/UFF |
| Cláudio Leonardo Lucchesi | IC/UNICAMP |
| Cândida Nunes da Silva | DCOMP/UFSCAR |
Suplentes:
| Guilherme Pimentel Telles | IC/UNICAMP |
| José Coelho de Pina Junior | IME/USP |