Sparse graphs

From Egres Open
Jump to: navigation, search

For positive integers k and l a graph G=(V,E) is called (k,l)-sparse if iG(X)k|X|l holds for every XV, |X|l/k. If |E|=k|V|l we say that G is a (k,l)-graph. For characterizations of (k,l)-sparse graphs, see the paper of Fekete and Szegő [1] and Lee and Streinu [2].

References

  1. Zs. Fekete, L. Szegő, A Note on [k,l]-sparse graphs, DOI link, EGRES Technical Report.
  2. A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, DOI link, arXiv link.