JISE

    A k-tree is defined recursively as follows. The complete graph K_k on k points is a k-tree. Given a k-tree G on n≧k points, a k-tree on n +1 points is obtained by adding a new point u and edges connecting u to every point of a K_h in G. A graph is a partial k-tree if it is: a subgraph of some k-tree.G is said to be minimal if G is not a partial k-tree but all its proper subgraphs are. In this paper, we construct some interesting properties of partial 3-trees in terms of minimal graphs and show that a graph is a partial 3-tree if and only if it has no subgraph that is minimal. Complete characterization of the class of minimal non-partial 3-trees is also established.