Balanced graphs and network flows

Balanced graphs and network flows

0.00 Avg rating0 Votes
Article ID: iaor2002402
Country: United States
Volume: 29
Issue: 2
Start Page Number: 77
End Page Number: 80
Publication Date: Mar 1997
Journal: Networks
Authors:
Keywords: graphs
Abstract:

A graph G is 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.

Reviews

Required fields are marked *. Your email address will not be published.