Soft 3-stars in sparse plane graphs

O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1863-1868

Résumé

We consider plane graphs with large enough girth $g$, minimum degree $\delta$ at least 2 and no $(k+1)$-paths consisting of vertices of degree 2, where $k\ge1$. In 2016, Hudák, Maceková, Madaras, and Široczki studied the case $k=1$, which means that no two 2-vertices are adjacent, and proved, in particular, that there is a 3-vertex whose all three neighbors have degree 2 (called a soft 3-star), provided that $g\ge10$, which bound on $g$ is sharp. For the first open case $k=2$ it was known that a soft 3-star exists if $g\ge14$ but may not exist if $g\le12$. In this paper, we settle the case $k=2$ by presenting a construction with $g=13$ and no soft 3-star. For all $k\ge3$, we prove that soft 3-stars exist if $g\ge4k+6$ but, as follows from our construction, possibly not exist if $g\le3k+7$. We conjecture that in fact soft 3-stars exist whenever $g\ge3k+8$.

Détail

Keywords: plane graph, structure properties, girth, tight description, weight, height, 3-star, soft 3-star.