Premium
Balanced graphs and network flows
Author(s) -
Penrice Stephen G.
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199703)29:2<77::aid-net1>3.0.co;2-8
Subject(s) - combinatorics , mathematics , lexicographical order , indifference graph , graph product , 1 planar graph , pathwidth , discrete mathematics , graph , chordal graph , line graph
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. © 1997 John Wiley & Sons, Inc.