We thoroughly explore the class of k-step nilpotent Lie algebras associated with a simple graph looking for k-step nilpotent Lie algebras which are rigid in the variety of at most k-step nilpotent Lie algebras. We find out that, besides the complete graph, the only examples arise for k = 2 and graphs of at most 4 vertices. A key tool to prove non-k-rigidity in this context, is a general construction of non-trivial deformations for naturally graded nilpotent Lie algebras.
Barrionuevo et al. (Fri,) studied this question.