scientific article; zbMATH DE number 15501

[For the entire collection see Zbl 0699.00014.] Let \(v(G)\) and \(e(G)\) denote the number of vertices and edges of a graph \(G\). The extremal problem considered involves the average degree of \(G\), \[ {1 \over v(G)} \sum_{x\in V(G)}\deg x={2e(G) \over v(G)}. \] To simplify the notation call \[ d(G)={e(G) \over v(G)} \] the degree of \(G\). If \(d(H)\leq d(G)\) for all subgraphs \(H\) of \(G\), then \(G\) is called balanced. Note that \(G\) balanced implies that every connected component of \(G\) is balanced and has the same degree. Note also that every regular graph is balanced, and it is easy to check that every tree is balanced. Furthermore, for connected graphs, \(d(G)<1\) if \(G\) is a tree and \(d(G)\geq 1\) otherwise.

Recommendations

Cited in

(8)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972136)