کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651083 1632445 2007 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Pairs of trees in tree–tree triangulations
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Pairs of trees in tree–tree triangulations
چکیده انگلیسی

A triangulation TT of a compact 2-manifold is said to be a tree–tree triangulation if the graph of TT can be partitioned into two induced trees. Hence each tree–tree triangulation is a triangulation of the 2-sphere. Recognizing tree–tree triangulations among all simple spherical ones can be seen to be an NP-complete problem. Some (exponentially many) pairs of trees into which graphs of some simple triangulations can be partitioned are characterized. In particular, for a pair made up of any tree and any long enough path, there is a spherical triangulation whose graph is partitionable into that pair.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1499–1505
نویسندگان
, ,