Previous [1] [2] [3] [4] [5] [6]

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 Kk 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 Kh 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.