×

zbMATH — the first resource for mathematics

Graph algebras and graph varieties. (English) Zbl 0725.08002
Let \(G=(V,E)\) be a directed graph without multiple edges, V denotes the set of vertices, E is the set of edges. Let \(\infty\) be an adjoined element. The operation \(a,b=a\) if (a,b)\(\in E\) and \(a,b=\infty\) otherwise defines the graph algebra on \(V\cup \{\infty \}\). The author proves a “Birkhoff-type” theorem: a class of finite directed graphs is a graph variety iff it is closed with respect to finite restricted pointed subproducts and isomorphic copies. Several applications are given.

MSC:
08B05 Equational logic, Mal’tsev conditions
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baker, K., McNulty, G. andWerner, H.,The finitely based varieties of graph algebras. Acta Sci. Math (Szeged)51 (1987), 3-15. · Zbl 0629.08003
[2] Hedetniemi, S. T.,Homomorphisms of graphs and automata. University of Michigan Technical Report 03105-44-T (1966).
[3] Hell, P.,An introduction to the category of graphs. Ann. N.Y. Acad. Sci.328 (1919), 120-136.
[4] Jónsson, B.,Varieties of relation algebras. Algebra Universalis15 (1982), 273-298. · Zbl 0545.08009
[5] Kiss, E.,A note on varieties of graph algebras. Proceedings Charleston Conference, Lecture Notes in Mathematics1149 (1985), 163-166. · Zbl 0572.08009
[6] McNulty G. F. andShallon, C. R.,Inherently nonfinitely based finite algebras. Lecture Notes Math.1004 (1983), 206-231.
[7] Nowakowski, R. andRival, I.,The smallest graph variety containing all paths. Discrete Math.43 (1983), 223-234. · Zbl 0511.05059
[8] Oates-Williams, Sh.,Murskii’s algebra does not satisfy MIN. Bull. Austral. Math. Soc.22 (1980), 199-203. · Zbl 0487.08008
[9] Oates-Williams, Sh.,Graphs and universal algebras. Lecture Notes Math.884 (1981), 351-354.
[10] Oates-Williams, Sh.,On the variety generated by Murskii’s algebra. Algebra Universalis18 (1984), 175-177. · Zbl 0542.08004
[11] Pöschel, R.,Graph varieties. Preprint P-MATH-18/85, Institut f. Math., Berlin 1985.
[12] Pöschel, R., andWessel, W.,Classes of graphs definable by graph algebra identities or quasiidentities. Comment. Math. Univ. Carolinae28 (1987), 581-592. · Zbl 0621.05030
[13] Pouzet, M. andRosenberg, I. G.,Embeddings and absolute retracts of relational systems. Preprint CRM-1265, Montreal, February 1985.
[14] Shallon, C. R.,Nonfinitely based finite algebras derived from lattices. Ph.D. Dissertation, University of California, Los Angeles, 1979.
[15] Tarski, A.,On the calculus of relations. J. Symbolic Logic6 (1941), 73-89. · Zbl 0026.24401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.