Grafos Half Cut

  • Rubens A. Sucupira
  • Sulamita Klein
  • Luerbio Faria
DOI: https://doi.org/10.5753/etc.2017.3193

Resumo


[Erdo¨s 1965] mostrou que todo grafo G = (V; E) com m arestas admite um corte de arestas com cardinalidade pelo menos m2 . Neste artigo definimos a classe de grafos Half Cut como os grafos que admitem um corte de arestas com cardinalidade igual a d m2 e. Nós também damos exemplos de grafos tais como caminhos, ciclos e grafos completos que devem satisfazer condições especiais para que sejam do tipo Half Cut.

Publicado
06/07/2017
Como Citar

Selecione um Formato
SUCUPIRA, Rubens A.; KLEIN, Sulamita; FARIA, Luerbio. Grafos Half Cut. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3193.