Graph theoretic closure properties of the family of boundary NLC graph languages (Q1084870)

The paper considers finite undirected graphs with labelled vertices. A node label controlled (NLC) grammar is a system \(G=(\Sigma,\Delta,P,conn,Z_{ax})\), where \(\Sigma\) is a set of labels, \(\Delta\) is its subset (the set of terminals), P is the set of productions (d,Y) for \(d\in \Sigma\) and Y being a graph labelled by \(\Sigma\), conn is a function from \(\Sigma\) into \(2^{\Sigma}\), and \(Z_{ax}\) is a graph labelled by \(\Sigma\) and called an axiom. Such a grammar describes the production of graphs in such a way that a vertex is replaced by a graph; the adjacency of vertices of this graph and of the neighbourhood of the replaced vertex is given by the labelling and by the function conn. The class of graphs obtained in such a way starting from the graph \(Z_{ax}\) is called an NLC language. A particular case of NLC languages are bounded NLC (BNLC) languages which are studied in this paper. It is proved that the set of all induced subgraphs of graphs from a BNLC language is again a BNLC language. Also the set of all k- colourable graphs, all connected graphs, all diconnected graphs, all graphs having a subgraph homeomorphic to a given graph in a BNLC language form again a BNLC language.