1990/05/01 by A. Satyanarayana, L. Tung · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Interconnection Networks and Systems #Combinatorics #Mathematics #Contractible space #Tree (set theory) #Graph #K-ary tree #Characterization (materials science) #Discrete mathematics #Binary tree #Tree structure #Physics
paper · doi:10.1002/net.3230200304
openalex publication_date 1990/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
Abstract 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 k in G . A graph is a partial k‐tree if it is a subgraph of some k ‐tree. In this paper, we establish some interesting properties of partial 3‐trees and show that a graph is a partial 3‐tree if and only if it has no subgraph contractible to K 5 , K 2.2.2 C 8 (1, 4), or K 2 ≤ C 5 . A graph G is said to be contractible to a graph H if H can be obtained from G by a sequence of edge contractions. hitherto, such a characterization of partial k ‐trees was known only for the values of k ≤ 2.