کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874168 1441026 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Light paths and edges in families of outer-1-planar graphs
ترجمه فارسی عنوان
مسیرهای نور و لبه ها در خانواده های گراف های بیرونی 1-پلان
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
It is proved that (1) every maximal outer-1-planar graph of order at least k contains a path on k-vertices with all vertices of degree at most 2k+1 (being sharp for k≤3), and a path on k-vertices with degree sum at most 5k−1, and further, (2) every maximal outer-1-planar graph contains an edge xy with d(x)+d(y)≤7, and every outer-1-planar graph with minimum degree at least 2 contains an edge xy with d(x)+d(y)≤9. Here the bounds 7 and 9 are sharp.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 136, August 2018, Pages 83-89
نویسندگان
, , , ,