Half-Cuts in Complete Bipartite Graphs
Abstract
A graph is Half Cut if it admits an edge cut with exactly [m/2] edges. It is known that graceful graphs are Half Cut and that complete bipartite graphs are graceful. In this paper we give an alternative proof that complete bipartite graphs are Half Cut, exhibiting an edge cut with exactly [m/2] edges.
References
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.
Published
2018-07-26
How to Cite
SUCUPIRA, Rubens A.; KLEIN, Sulamita; FARIA, Luerbio.
Half-Cuts in Complete Bipartite Graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
