Undecidability of the bandwidth problem on linear graph languages (Q908714)

Let \(G=(V,E)\) be an undirected graph with n vertices. The graph G has bandwidth k if there exists (1-1) mapping (k-layout) f: \(V\to \{1,2,...,n\}\), such that \(| f(u)-f(v)| \leq k\) for each edge \(\{\) u,v\(\}\in E\). Let \(\Gamma\) be a linear graph grammar defined as follows. \(\Gamma\) consists of a finite number of labelled undirected graphs \(G_ 1,G_ 2,...,G_ k\) such that each of them has at most one vertex labelled with p, one vertex labelled with q (connection vertices), and one vertex labelled with \(\delta\) (nonterminal vertex). Each nonterminal vertex u has exactly two neighbor vertices labelled p' and q' and some substitution rules \(u\to G_ t\), \(t\in \{1,2,...,k\}\). One of the graphs \(G_ t\) is the start graph. In \(\Gamma\) a graph G directly derives into a graph J if G contains a nonterminal vertex u with substitution rule \(u\to G_ t\) and is obtained by substitution u of a copy \(G_ t\) of \(G_ t\) with the identification vertices p and q with vertices p' and q' respectively. In \(\Gamma\) a graph G derives into a graph J if there exists a sequence of graphs \(H_ 1,H_ 2,...,H_{\ell}\), \((1>1)\), \(G=H_ 1\), \(J=H_{\ell}\), and \(H_ i\) directly derives into \(H_{i+1}\), \(i=1,2,...,l-1\). The language L(\(\Gamma)\) of \(\Gamma\) is defined as a set of graphs that are derivable from the start graph and have no nonterminal vertices. The main result: Theorem 1. Let \(\Gamma\) be a linear graph grammar and \(k\geq 3\) be an integer. Then the following question is undecidable: does the language L(\(\Gamma)\) contain a graph G having bandwidth k ? The proof of the theorem consists in reducing of well-known Post's correspondence problem, which is known to be undecidable, to this problem. For the case \(k=2\) the authors conjecture that Theorem 1 does not hold.