Sparse graphs
From Egres Open
For positive integers k and l a graph G=(V,E) is called [math](k,l)[/math]-sparse if [math]i_G(X)\leq k|X|-l[/math] holds for every [math]X\subseteq V[/math], [math]|X|\geq l/k[/math]. If [math]|E|=k|V|-l[/math] we say that G is a [math](k,l)[/math]-graph. For characterizations of [math](k,l)[/math]-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.
