RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2020, том 17, страницы 1863–1868 (Mi semr1320)

Дискретная математика и математическая кибернетика

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



Реферативные базы данных:


© МИАН, 2024