Optimal unavoidable sets of types of 3-paths for planar graphs of given girth

详细信息    查看全文

• 作者：S. Jendrol&rsquo ; ^a ; ^{stanislav.jendrol@upjs.sk" class="auth_mail" title="E-mail the corresponding author} ; M. Maceková ; ^a ; ^{maria.macekova@student.upjs.sk" class="auth_mail" title="E-mail the corresponding author} ; M. Montassier^b ; ^{mickael.montassier@lirmm.fr" class="auth_mail" title="E-mail the corresponding author} ; R. Sotá ; k^a ; ^{roman.sotak@upjs.sk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Girth ; Optimal unavoidable set ; 3-path ; Planar graph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：780-789
• 全文大小：519 K

文摘

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 g$g$. A 3-path of type bded0e5" title="Click to view the MathML source">(i,j,k)$(i,j,k)$ is a path uvw$uvw$ on three vertices u$u$, v$v$, and w$w$ such that the degree of u$u$ (resp. v$v$, resp. w$w$) is at most i$i$ (resp. j$j$, resp. k$k$). The elements i,j,k$i,j,k$ are called parameters   of the type. The set bde97af1b2d16aecdf70" title="Click to view the MathML source">S$S$ of types of paths is unavoidable   for a family F$\mathcal{F}$ of graphs if each graph G$G$ from F$\mathcal{F}$ contains a path of the type from bde97af1b2d16aecdf70" title="Click to view the MathML source">S$S$. An unavoidable set bde97af1b2d16aecdf70" title="Click to view the MathML source">S$S$ of types of paths is optimal   for the family F$\mathcal{F}$ if neither any type can be omitted from bde97af1b2d16aecdf70" title="Click to view the MathML source">S$S$, nor any parameter of any type from bde97af1b2d16aecdf70" title="Click to view the MathML source">S$S$ can be decreased.

We prove that the set S_g$S_g$ (resp. S^′_g$S^{\prime }{}_g$) is an optimal set of types of 3-paths for the family of plane graphs having δ(G)≥2$\delta \left(G\right)\ge 2$ and girth g(G)≥g$g\left(G\right)\ge g$ where

(i)

196611a474c514944f946207efa59b87" title="Click to view the MathML source">S₅={(2,∞,2),(2,3,5),(2,4,3),(3,3,3)}$S_5=\{(2,\infty ,2),(2,3,5),(2,4,3),(3,3,3)\}$,

(ii)

S₇={(2,3,3),(2,5,2)}$S_7=\{(2,3,3),(2,5,2)\}$,

$S_7^{\prime }=\{(2,2,6),(2,3,3),(2,4,2)\}$,

(iii)

S₈={(2,2,5),(2,3,2)}$S_8=\{(2,2,5),(2,3,2)\}$,

(iv)

S₁₀={(2,4,2)}$S_{10}=\left\{(2,4,2)\right\}$,

$S_{10}^{\prime }=\{(2,2,3),(2,3,2)\}$,

(v)

S₁₁={(2,2,3)}$S_{11}=\left\{(2,2,3)\right\}$.