Эта публикация цитируется в
1 статье
Дискретная математика и математическая кибернетика
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, Hudák, Maceková, Madaras, and Š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$, Hudá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.
УДК:
519.172.2
MSC: 05C75 Поступила 9 октября 2018 г., опубликована
1 ноября 2018 г.
Язык публикации: английский
DOI:
10.17377/semi.2018.15.110