95-23 Balanced Graphs and Network Flows

DIMACS TR: 95-23

Balanced Graphs and Network Flows

Author: Stephen Penrice

ABSTRACT
A graph $G$ is {\em balanced\/} if the maximum ratio of edges to vertices, taken over all subgraphs of $G$, occurs at $G$ itself. This note uses the max-flow/min-cut theorem to prove a good characterization of balanced graphs. This characterization is then applied to some results on how balanced graphs may be combined to form a larger balanced graph. In particular, we show that edge-transitive graphs and complete $m$-partite graphs are balanced, that a product or lexicographic product of balanced graphs is balanced, and that the normal product of a balanced graph and a regular graph is balanced.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-23.ps.gz

DIMACS Home Page