Article ID Journal Published Year Pages File Type
4650601 Discrete Mathematics 2008 13 Pages PDF
Abstract

A multi-graph G on n   vertices is (k,ℓ)(k,ℓ)-sparse if every subset of n′⩽nn′⩽n vertices spans at most kn′-ℓkn′-ℓ edges. G is tight   if, in addition, it has exactly kn-ℓkn-ℓ edges. For integer values k   and ℓ∈[0,2k)ℓ∈[0,2k), we characterize the (k,ℓ)(k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)(k,ℓ)-pebble games.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,