Braces minimais e suas propriedades

• Ano de defesa: 2021
• Autor(a) principal: Phelipe Araujo Fabres
• Orientador(a): Marcelo Henriques de Carvalho
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Fundação Universidade Federal de Mato Grosso do Sul
• País: Brasil
• Palavras-chave em Português: emparelhamento perfeito, grafo bipartido, grafo coberto por emparelhamentos, brick, brace, grafo 2-extensível.
• Link de acesso: https://repositorio.ufms.br/handle/123456789/4185

McCuaig proved a generation theorem for braces, and used it as the principal induction tool to obtain a structural characterization of Pfaffian braces. A brace is minimal if deleting any edge results in a graph that is not a brace. From McCuaig’s brace generation theorem, we derive our main theorem that may be viewed as an induction tool for minimal braces. As an application, we prove that a minimal brace of order 2n has size at most 5n − 10, when n ≥ 6, and we provide a complete characterization of minimal braces that meets this upper bound. A similar work has already been done in the context of minimal bricks by Norine-Thomas wherein they deduce the main result from the brick generation theorem due to the same authors. Therefore, we built a definitive version, combining an alternative proof of Norine-Thomas’s theorem with our main theorem, for building minimal bricks and braces.