The paper discusses some ways to strengthen (nonasymptotically) the Gilbert
-Varshamov bound for linear codes. The unifying idea is to study a certain
graph constructed on vectors of low weight in the cosets of the code, which
we call the Varshamov graph. Various simple estimates of the number of its
connected components account for better lower bounds on the minimum distan
ce of codes, some of them known in the literature. (C) 2000 Elsevier Scienc
e Inc. All rights reserved.