Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420861 | Discrete Applied Mathematics | 2006 | 8 Pages |
Abstract
A k-tree is either a complete graph on k vertices or a graph G=(V,E)G=(V,E) that contains a vertex whose neighbourhood in G induces a complete graph on k vertices and whose removal results in a k-tree. We present two new subclasses of k-trees and their properties. First, we present the definition and characterization of k-path graphs, based on the concept of k-paths, that generalizes the classic concept of paths. We also introduce the simple-clique k-trees, of which the maximal outerplanar graphs and the planar 3-trees are particular cases. Based on Characterization Theorems, we show recognition algorithms for both families. Finally, we establish the inclusion relations among these new classes and k-trees.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
L. Markenzon, C.M. Justel, N. Paciornik,