کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646676 1342309 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal unavoidable sets of types of 3-paths for planar graphs of given girth
ترجمه فارسی عنوان
مجموعه های اجتناب ناپذیر مطلوب از انواع 3 مسیر برای نمودارهای مسطح از محدوده داده شده
کلمات کلیدی
غرق شدن مجموعه بی نظیر مطلوب، 3 مسیر، نمودار پلانار
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

In this paper we study unavoidable sets of types of 3-paths for families of planar graphs with minimum degree at least 2 and a given girth gg. A 3-path of type (i,j,k)(i,j,k) is a path uvwuvw on three vertices uu, vv, and ww such that the degree of uu (resp. vv, resp. ww) is at most ii (resp. jj, resp. kk). The elements i,j,ki,j,k are called parameters   of the type. The set SS of types of paths is unavoidable   for a family FF of graphs if each graph GG from FF contains a path of the type from SS. An unavoidable set SS of types of paths is optimal   for the family FF if neither any type can be omitted from SS, nor any parameter of any type from SS can be decreased.We prove that the set SgSg (resp. S′gS′g) is an optimal set of types of 3-paths for the family of plane graphs having δ(G)≥2δ(G)≥2 and girth g(G)≥gg(G)≥g where (i)S5={(2,∞,2),(2,3,5),(2,4,3),(3,3,3)}S5={(2,∞,2),(2,3,5),(2,4,3),(3,3,3)},(ii)S7={(2,3,3),(2,5,2)}S7={(2,3,3),(2,5,2)},S7′={(2,2,6),(2,3,3),(2,4,2)},(iii)S8={(2,2,5),(2,3,2)}S8={(2,2,5),(2,3,2)},(iv)S10={(2,4,2)}S10={(2,4,2)},S10′={(2,2,3),(2,3,2)},(v)S11={(2,2,3)}S11={(2,2,3)}.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 780–789
نویسندگان
, , , ,