3
$\begingroup$

What are some quantities often used to measure the sparseness of a graph?

  1. For example, in a graph, with the number of vertices fixed, the smaller the maximum degree is, the more sparse the graph is. With the maximum degree fixed, the bigger the number of vertices is, the more sparse the graph is.
  2. For another example, the more sparse the adjacent matrix is, the more sparse the graph is. Then it leads to another question: what are some quantities to measure the sparseness of a matrix?

Thanks!

  • 0
    I've seen 'sparse' and 'dense' for a collection of graphs defined as the number of edges growing as O(n) and O(n^2) respectively - n being the number of nodes.2014-06-11

0 Answers 0