Discrete mathematics and mathematical cybernetics
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
Abstract:
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$.
Keywords:
plane graph, structure properties, girth, tight description, weight, height, 3-star, soft 3-star.
UDC:
519.172.2
MSC: 05C75 Received September 4, 2020, published
November 18, 2020
DOI:
10.33048/semi.2020.17.126