The extremely wide applicability of graphs in computer science and elsewhere has insured an ever-growing interest in graph grammars and graph languages. This paper concerns node-label controlled (NLC) graph grammars, introduced by D. Janssens and G. Rozenberg some ten years ago. The application of a rule of an NLC grammar is controlled by a connection relation, which determines how the nodes of its right side are to be connected with the nodes in the neighborhood of the rewritten node. Here the special case of a one-letter terminal node label alphabet is considered.

The first set of results shows that some natural restrictions on the connection relation, which researchers hoped would lead to normal forms of NLC grammars, properly limit the generating power of NLC grammars even in this one-letter case; for larger alphabets this had already been known. Next, some negative closure properties are shown: the class of NLC graph languages is not closed under intersection, complements, dualization, or edge complementation. Finally, the authors prove that restricting derivations to neighborhood-preserving steps yields a family of graph languages incomparable with the family of NLC graph languages. In all cases one-letter examples are given.