
Sib. Èlektron. Mat. Izv., 2018, Volume 15, Pages 1344–1352
(Mi semr1001)




Discrete mathematics and mathematical cybernetics
Light 3stars in sparse plane graphs
O. V. Borodin^{a}, A. O. Ivanova^{b} ^{a} Sobolev Institute of Mathematics,
pr. Koptyuga, 4,
630090, Novosibirsk, Russia
^{b} Ammosov NorthEastern Federal University,
str. Kulakovskogo, 48,
677000, Yakutsk, Russia
Abstract:
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 degreesum 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 3polytope of girth $g$ at least 5 has a 2star (a path of three vertices) with $h_2=3$ and $w_2=9$. Madaras (2004) refined this by showing that there is a 3star with $h_3=4$ and $w_3=13$, which is tight.
In 2015, we gave another tight description of 3stars for girth $g=5$ in terms of degree of their vertices and showed that there are only these two tight descriptions of 3stars.
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, 3star, girth.
DOI:
https://doi.org/10.17377/semi.2018.15.110
Full text:
PDF file (639 kB)
References:
PDF file
HTML file
Bibliographic databases:
Document Type:
Article
UDC:
519.172.2
MSC: 05C75 Received October 9, 2018, published November 1, 2018
Language: English
Citation:
O. V. Borodin, A. O. Ivanova, “Light 3stars in sparse plane graphs”, Sib. Èlektron. Mat. Izv., 15 (2018), 1344–1352
Citation in format AMSBIB
\Bibitem{BorIva18}
\by O.~V.~Borodin, A.~O.~Ivanova
\paper Light 3stars in sparse plane graphs
\jour Sib. \`Elektron. Mat. Izv.
\yr 2018
\vol 15
\pages 13441352
\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}
Linking options:
http://mi.mathnet.ru/eng/semr1001 http://mi.mathnet.ru/eng/semr/v15/p1344
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  22  Full text:  6 
