Combinatorial properties of boundary NLC graph languages

DOI10.1016/0166-218X(87)90054-0MaRDI QIDQ1089808zbMATH OpenOpenAlexWikidataFDO

Authors Grzegorz Rozenberg, Emo Welzl

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(87)90054-0

zbMATH Keywords

adjacency structurebehaviour of graph invariantsBNLC languageschromatic numberclique numbergraph grammarsindex of a graphnode label controlled grammarsnode labeled undirected graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Formal languages and automata (68Q45)

Review text

Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs) which rewrite single nodes only and establish connections between the embedded graph and the neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels, languages of unlabeled graphs). Boundary NLC (BNLC) grammars are NLC grammars with the property that whenever - in a graph already generated - two nodes may be rewritten, then these nodes are not adjacent. The graph languages generated by this type of grammars are called BNLC languages. In this paper we investigate the behaviour of graph invariants within BNLC languages. First we demonstrate that there is a dependency between the chromatic number and the clique number of graphs in BNLC languages (while this is well-known not to be true for arbitrary graph languages). Secondly, we introduce a new graph invariant, the so-called index of a graph which seems to be very suitable for describing the adjacency structure of a graph. Then we prove that every BNLC language is of bounded index (which is shown not to be true for arbitrary graph languages). Thus we exhibit properties (concerning graph invariants) of BNLC languages which are intrinsic to this class. We use them to demonstrate that certain graph languages are not BNLC languages.

Recommendations

• Graph theoretic closure properties of the family of boundary NLC graph languages
• scientific article; zbMATH DE number 3890755
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• The generating power of boundary NLC graph grammars and cycle graphs
• scientific article; zbMATH DE number 3943059

Cites work

• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Decision problems for node label controlled graph grammars
• Graph theoretic closure properties of the family of boundary NLC graph languages
• Graph theory
• scientific article; zbMATH DE number 3644498 (Why is no real title available?)
• scientific article; zbMATH DE number 3885330 (Why is no real title available?)
• scientific article; zbMATH DE number 3852433 (Why is no real title available?)
• scientific article; zbMATH DE number 3633737 (Why is no real title available?)
• On the structure of node-label-controlled graph languages
• Parallel concepts in graph theory
• Restrictions on NLC graph grammars
• Restrictions, extensions, and variations of NLC grammars
• Sur le coloriage des graphs

Cited in

(19)

• Graph theoretic closure properties of the family of boundary NLC graph languages
• Algorithms for graph problems on BNLC structured garphs
• On hyperedge replacement and BNLC graph grammars
• Separating \(k\)-separated eNCE graph languages
• A pumping lemma and the structure of derivations in the boundary NLC graph languages
• The complexity of connectivity problems on context-free graph languages
• The generating power of boundary NLC graph grammars and cycle graphs
• Logical description of context-free graph languages
• Linear graph grammars: Power and complexity
• A normal form problem for unlabeled boundary NLC graph languages
• A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions
• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
• scientific article; zbMATH DE number 3890755 (Why is no real title available?)
• scientific article; zbMATH DE number 3943059 (Why is no real title available?)
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• Nonterminal separation in graph grammars
• Boundary graph grammars with dynamic edge relabeling
• A comparison of boundary graph grammars and context-free hypergraph grammars

This page was built for publication: Combinatorial properties of boundary NLC graph languages

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