Sparse graphs
From Egres Open
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 X⊆V, |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
- ↑ Zs. Fekete, L. Szegő, A Note on [k,l]-sparse graphs, DOI link, EGRES Technical Report.
- ↑ A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, DOI link, arXiv link.