Half Cuts em Grafos Bipartidos Completos
Resumo
Um grafo é Half Cut se admite um corte de arestas de cardinalidade [m/2]. É sabido que grafos graciosos são Half Cut e os grafos bipartidos completos são graciosos. Neste artigo damos uma prova alternativa de que os grafos bipartidos completos são Half Cut, exibindo um corte de arestas de cardinalidade [m/2].
Referências
Acharya, B. and Gill, M. (1981). On the index of gracefulness of a graph and the gracefulness of two-dimensional square lattice graphs. Indian J. Math, 23:81–94.
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.
Sucupira, R., Faria, L., and Klein, S. (2017). Grafos half cut. In de Computação, S. B., editor, Anais do XXXVII Congresso da SBC, pages 115–118. XXXVII Congresso da Sociedade Brasileira de Computação.
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.
Sucupira, R., Faria, L., and Klein, S. (2017). Grafos half cut. In de Computação, S. B., editor, Anais do XXXVII Congresso da SBC, pages 115–118. XXXVII Congresso da Sociedade Brasileira de Computação.
Publicado
26/07/2018
Como Citar
SUCUPIRA, Rubens A.; KLEIN, Sulamita; FARIA, Luerbio.
Half Cuts em Grafos Bipartidos Completos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 97-100.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3161.
