کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420861 683993 2006 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Subclasses of k-trees: Characterization and recognition
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Subclasses of k-trees: Characterization and recognition
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 5, 1 April 2006, Pages 818–825
نویسندگان
, , ,