Exact bounds for judicious partitions of graphs (Q1977429)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Exact bounds for judicious partitions of graphs |
scientific article |
Statements
Exact bounds for judicious partitions of graphs (English)
0 references
14 May 2000
0 references
Extending a result of \textit{C. S. Edwards} [Can. J. Math. 25, 475-485 (1973; Zbl 0229.05129) and Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 167-181 (1975; Zbl 0326.05115)] it is shown that a graph with \(m\) edges has a bipartition with at least \(t=m/2 + (\sqrt{8m+1}-1)/8\) edges and at most \(t/2\) inner edges in either class. This result is sharp for complete graphs of odd order which are the only extremal graphs with no isolated vertices. Similar results are proved for the case of more classes.
0 references
extremal graph theory
0 references