کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646676 | 1342309 | 2016 | 10 صفحه PDF | دانلود رایگان |
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)}.
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 780–789