scientific article; zbMATH DE number 4087049

From MaRDI portal
Publication:3815541





The paper under review is a very short discussion of the following problem: Given a graph property Q and a class of graph grammars, does Q hold for all (resp.: for some) graphs generated by a grammar of this class? The authors restrict the notion of graph grammar to the hyperedge replacement systems. In this case, it can be shown that both versions of the problem are decidable if Q is (in some sense) compatible with the derivation process. Colorability, connectivity, cycle freeness, planarity, and the existence of Hamiltonian and Eulerian paths are some examples of compatible properties. The paper is clearly written, but it does not contain any proofs. The interested reader can find some of them in the first author's WG 88 paper [Graph-theoretic properties compatible with graph derivations, Lect. Notes Comput. Sci. 344, 11-29 (1989)].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815541)