کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902982 1632398 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Thickness and outerthickness for embedded graphs
ترجمه فارسی عنوان
ضخامت و بیرونی برای نمودار های تعبیه شده
ترجمه چکیده
با استفاده از روش حذف قطعه های پشته سازی جاسازی ها برای تقریبی ضخامت و ضخامت بیرونی، مرزهای بالایی جدیدی را برای ضخامت و بیرونی گراف به دست می آوریم. ما همچنین نشان می دهیم که هر گراف غیر تورباری غیر مسطح می تواند لبه را به یک نمودار مسطح و یک نمودار بیرونی پلان تقسیم کند. این بدان معنی است که بیرونی توری (حداکثر بیثبیت کلیه تمام نمودارهای توریال) 3 است. در نهایت، ما نشان می دهیم که تمام گرافهای قابل تعویض در دو طرف دارای ضخامت بیشتر از 3 و بیرونی کمترین 5 هستند.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We prove new upper bounds for the thickness and outerthickness of a graph in terms of its orientable and nonorientable genus by applying the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness. We also show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This implies that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. Finally, we show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 6, June 2018, Pages 1688-1695
نویسندگان
, ,