RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
 Общая информация Последний выпуск Архив Импакт-фактор Поиск публикаций Поиск ссылок RSS Последний выпуск Текущие выпуски Архивные выпуски Что такое RSS

 Сиб. электрон. матем. изв.: Год: Том: Выпуск: Страница: Найти

 Персональный вход: Логин: Пароль: Запомнить пароль Войти Забыли пароль? Регистрация

 Сиб. электрон. матем. изв., 2018, том 15, страницы 1344–1352 (Mi semr1001)

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

Light 3-stars in sparse plane graphs

O. V. Borodina, A. O. Ivanovab

a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Ammosov North-Eastern Federal University, str. Kulakovskogo, 48, 677000, Yakutsk, Russia

Аннотация: A $k$-star $S_k(v)$ in a plane graph $G$ consists of a central vertex $v$ and $k$ its neighbor vertices. The height $h(S_k(v))$ and weight $w(S_k(v))$ of $S_k(v)$ is the maximum degree and degree-sum of its vertices, respectively. The height $h_k(G)$ and weight $w_k(G)$ of $G$ is the maximum height and weight of its $k$-stars.
Lebesgue (1940) proved that every 3-polytope of girth $g$ at least 5 has a 2-star (a path of three vertices) with $h_2=3$ and $w_2=9$. Madaras (2004) refined this by showing that there is a 3-star with $h_3=4$ and $w_3=13$, which is tight. In 2015, we gave another tight description of 3-stars for girth $g=5$ in terms of degree of their vertices and showed that there are only these two tight descriptions of 3-stars.
In 2013, we gave a tight description of $3^-$-stars in arbitrary plane graphs with minimum degree $\delta$ at least 3 and $g\ge3$, which extends or strengthens several previously known results by Balogh, Jendrol', Harant, Kochol, Madaras, Van den Heuvel, Yu and others and disproves a conjecture by Harant and Jendrol' posed in 2007.
There exist many tight results on the height, weight and structure of $2^-$-stars when $\delta=2$. In 2016, Hudák, Maceková, Madaras, and Široczki considered the class of plane graphs with $\delta=2$ in which no two vertices of degree 2 are adjacent. They proved that $h_3=w_3=\infty$ if $g\le6$, $h_3=5$ if $g=7$, $h_3=3$ if $g\ge8$, $w_3=10$ if $g=8$ and $w_3=3$ if $g\ge9$. For $g=7$, Hudák et al. proved $11\le w_3\le20$.
The purpose of our paper is to prove that every plane graph with $\delta=2$, $g=7$ and no adjacent vertices of degree 2 has $w_3=12$.

Ключевые слова: plane graph, structure properties, tight description, weight, 3-star, girth.

 Финансовая поддержка Номер гранта Российский фонд фундаментальных исследований 18-01-00353_a16-01-00499_a Министерство образования и науки Российской Федерации 1.7217.2017/6.7 The first author was supported by the Russian Foundation for Basic Research (grants 18-01-00353 and 16-01-00499). The second author's work was performed as a part of government work “Leading researchers on an ongoing basis” (1.7217.2017/6.7).

DOI: https://doi.org/10.17377/semi.2018.15.110

Полный текст: PDF файл (639 kB)
Список литературы: PDF файл   HTML файл

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

Тип публикации: Статья
УДК: 519.172.2
MSC: 05C75
Поступила 9 октября 2018 г., опубликована 1 ноября 2018 г.
Язык публикации: английский

Образец цитирования: O. V. Borodin, A. O. Ivanova, “Light 3-stars in sparse plane graphs”, Сиб. электрон. матем. изв., 15 (2018), 1344–1352

Цитирование в формате AMSBIB
\RBibitem{BorIva18} \by O.~V.~Borodin, A.~O.~Ivanova \paper Light 3-stars in sparse plane graphs \jour Сиб. электрон. матем. изв. \yr 2018 \vol 15 \pages 1344--1352 \mathnet{http://mi.mathnet.ru/semr1001} \crossref{https://doi.org/10.17377/semi.2018.15.110} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000454860200052} 

Образцы ссылок на эту страницу:
• http://mi.mathnet.ru/semr1001
• http://mi.mathnet.ru/rus/semr/v15/p1344

 ОТПРАВИТЬ:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
•  Просмотров: Эта страница: 109 Полный текст: 16 Литература: 6
 Обратная связь: math-net2021_01 [at] mi-ras ru Пользовательское соглашение Регистрация Логотипы © Математический институт им. В. А. Стеклова РАН, 2021