Characterization of partial 3-trees in terms of three structures (Q1086577)

A graph \(G=(V,E)\) (simple and undirected) is a k-tree if there exists a bijection \(A:\{1,2,...,n\}\to V\) \((| V| =n>k)\) such that \(\Lambda (A(p))=\Gamma (A(p))-\{A(1),...,A(p)\}\) forms a clique and \(| \Lambda (A(p))| =k\) for all \(p=1,...,n-k\). A graph \(G=(V,E)\) is called a partial k-tree if it can be extended by adding some edges into a k-tree \(H=(V,F)\), \(F\supset E\). The paper contains several assertions concerning characterization of partial k-trees for both general k and \(k=3\). Eventually, an algorithm with a polynomial \((O(n^ 2))\) time convexity is presented enabling to recognize 3-trees.