Grafos Half Cut
Resumo
[Erdös 1965] mostrou que todo grafo G = (V, E) com m arestas admite um corte de arestas com cardinalidade pelo menos m/2. Neste artigo definimos a classe de grafos Half Cut como os grafos que admitem um corte de arestas com cardinalidade igual a [m/2]. 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.
Referências
Erdös, P. (1965). On some extremal problems in graph theory. Israel Journal of Mathematics, 3:113–116.
Golomb, S. W. (1972). How to number a graph. Graph theory and computing, pages 23–37.
Huang, C., Kotzig, A., and Rosa, A. (1982). Further results on tree labellings. Util. math., 21c, pages 31–48.
Rosa, A. (1966). On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Symposium, Rome, pages 349–355.
Golomb, S. W. (1972). How to number a graph. Graph theory and computing, pages 23–37.
Huang, C., Kotzig, A., and Rosa, A. (1982). Further results on tree labellings. Util. math., 21c, pages 31–48.
Rosa, A. (1966). On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Symposium, Rome, pages 349–355.
Publicado
02/07/2017
Como Citar
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
.
p. 65-68.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2017.3193.
