Abstract. Shallon invented a means of deriving algebras from graphs, yielding numerous examples of so-called graph algebras with interesting equational properties. Here we study directed graph algebras, derived from directed graphs in the same way that Shallon's undirected graph algebras are derived from graphs. We classify the finitely based looped directed graph algebras and find the five finitely based varieties generated by them. We show that every looped directed graph algebra is either finitely based or inherently nonfinitely based. We find an equational basis for the variety generated by all directed graph algebras. We also develop a general two-part method for showing that varieties are finitely based; this method is then developed further, into syntactic and semantic components, in the specific case of varieties generated by directed graph algebras.

AMS Subject Classification (1991): 03C05; 08B15, 08B05

Keyword(s): Directed graph algebra, finite equational basis, finite basis problem, lattice of varieties, looped graphs, inherently nonfinitely based

Received August 30, 2004, and in revised form August 7, 2006. (Registered under 5930/2009.)