average degree

• 2019 Sorge2019
  • page 3 : average degree – The \emph{average degree} of a graph $G = (V,E)$ is $2|E|/|V|$.
• https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.3190120309
  • average degree – The average distance in a graph is defined as the average length of a shortest path between two vertices, taken over all pairs of vertices.
• unknown
  • degeneracy $k$ upper bounds average degree by $\mathcal O(k)$ – Removing a vertex of degree $d$ increases the value added to the sum of all degrees by at most $2d$, hence, the average is no more than twice the degeneracy.
  • average degree $k$ upper bounds minimum degree by $\mathcal O(k)$ – By definition
• https://bookdown.org/omarlizardo/_main/2-7-average-degree.html
  • average degree – Average degree is simply the average number of edges per node in the graph. … Total Edges/Total Nodes=Average Degree
• SchroderThesis
  • page 35 : bounded average degree does not imply bounded maximum clique – Proposition 3.35
  • page 36 : bounded average degree does not imply bounded chordality – Proposition 3.36