On strongly balanced graphs (Q1175026)

A graph \(G\) of order \(p\) and size \(q>0\) is said to be strongly balanced if for every nonempty subgraph of order \(n\) and size \(m\) of \(G\), \(m/(n- 1)\leq q/(p-1)\). It is shown that \(G\) with minimum degree one is strongly balanced if and only if \(G\) is a tree. A property \(Q\) of a graph \(G\) is called hereditary if every subgraph of \(G\) also has the property \(Q\). A graph \(G\) is said to be a maximal \(Q\) graph if \(G\) has the property \(Q\) but no edge can be added to \(G\) without loosing the property \(Q\). The authors prove that maximal \(Q\) graph are strongly balanced for several hereditary properties \(Q\). Finally, they show that a graph is strongly balanced if and only if its subdivision graph is strongly balanced.