Light 3-stars in sparse plane graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1344-1352

Voir la notice de l'article provenant de la source Math-Net.Ru

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$.
Keywords: plane graph, structure properties, tight description, weight, 3-star, girth.
@article{SEMR_2018_15_a76,
     author = {O. V. Borodin and A. O. Ivanova},
     title = {Light 3-stars in sparse plane graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1344--1352},
     publisher = {mathdoc},
     volume = {15},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - Light 3-stars in sparse plane graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2018
SP  - 1344
EP  - 1352
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/
LA  - en
ID  - SEMR_2018_15_a76
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T Light 3-stars in sparse plane graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2018
%P 1344-1352
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/
%G en
%F SEMR_2018_15_a76
O. V. Borodin; A. O. Ivanova. Light 3-stars in sparse plane graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1344-1352. http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/