Grafos Half Cut
Abstract
[Erdös 1965] showed that every graph G = (V, E) with m edges admits an edge cut of size at least m/2. In this paper we define a new graph class: Half Cut graphs. A graph is Half Cut if it admits an edge cut with exactly [m/2] edges. We also give some simple examples such as paths, cycles and complete graphs that must satisfy special conditions to be Half Cut graphs.
References
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.
Published
2017-07-02
How to Cite
SUCUPIRA, Rubens A.; KLEIN, Sulamita; FARIA, Luerbio.
Grafos Half Cut. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
