Journal of Inforamtion Science and Engineering, Vol.6 No.3, pp.191-209 (September 1990)

Minimal Graphs of Partial 3-Trees
**Sing-Bor Tong and Leeping Tung**^{+}

*Department of Mathematics
*

National Chen Kung University

Tainan, Taiwan 70101, Republic of China

^{+}Department of Electrical Engineering and Computer Science

Stevens Institute of Technology

Hoboken, New Jersey 07030, U.S.A.

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.

Keywords: minimal graphs, critical graphs, contractible, homeomorphic

Received November 15, 1989; revised April 11, 1990.

Communicated by Jhing-Fa Wang.