## 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