Article ID Journal Published Year Pages File Type
4646676 Discrete Mathematics 2016 10 Pages PDF
Abstract

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)}.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,