کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949615 1440197 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dense on-line arbitrarily partitionable graphs
ترجمه فارسی عنوان
انبوه بر روی خط نمودار اختیاری است
کلمات کلیدی
تقسیم نمودارها، نمودار قابل ردیابی شرایط شربت گالیله، سنگ معدن، تطبیق کامل،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that if G is a connected graph such with the independence number at most ⌈n2⌉ and the degree sum of any pair of non-adjacent vertices is at least n−3, then G is on-line arbitrarily partitionable except for two graphs of small orders. We also prove that if G is a connected graph of order n and size ‖G‖>n−32+6, then G is on-line AP unless n is even and G is a spanning subgraph of a unique exceptional graph. These two results imply that dense AP graphs satisfying one of the above two assumptions are also on-line AP. This is in contrast to sparse graphs where only few AP graphs are also on-line AP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 71-77
نویسندگان
,