Дискретная математика и математическая кибернетика
Soft $3$-stars in sparse plane graphs
O. V. Borodina,
A. O. Ivanovab a Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
b Ammosov North-Eastern Federal University, 48, Kulakovskogo str., Yakutsk, 677000, Russia
Аннотация:
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$.
Ключевые слова:
plane graph, structure properties, girth, tight description, weight, height, $3$-star, soft $3$-star.
УДК:
519.172.2
MSC: 05C75 Поступила 4 сентября 2020 г., опубликована
18 ноября 2020 г.
DOI:
10.33048/semi.2020.17.126