RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2016 Volume 57, Number 3, Pages 596–602 (Mi smj2765)

This article is cited in 14 papers

Light and low $5$-stars in normal plane maps with minimum degree $5$

O. V. Borodina, A. O. Ivanovab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
b Ammosov North-Eastern Federal University, Yakutsk, Russia

Abstract: It is known that there are normal plane maps (NPMs) with minimum degree $\delta=5$ such that the minimum degree-sum $w(S_5)$ of $5$-stars at $5$-vertices is arbitrarily large. The height of a $5$-star is the maximum degree of its vertices. Given an NPM with $\delta=5$, by $h(S_5)$ we denote the minimum height of a $5$-stars at $5$-vertices in it.
Lebesgue showed in 1940 that if an NPM with $\delta=5$ has no $4$-stars of cyclic type $(\overrightarrow{5,6,6,5})$ centered at $5$-vertices, then $w(S_5)<68$ and $h(S_5)<41$. Recently, Borodin, Ivanova, and Jensen lowered these bounds to $55$ and $28$, respectively, and gave a construction of a $(\overrightarrow{5,6,6,5})$-free NPM with $\delta=5$ having $w(S_5)=48$ and $h(S_5)=20$.
In this paper, we prove that $w(S_5)<51$ and $h(S_5)<23$ for each $(\overrightarrow{5,6,6,5})$-free NPM with $\delta=5$.

Keywords: graph, plane map, weight, light subgraph, height, low subgraph.

UDC: 519.17

Received: 17.09.2015

DOI: 10.17377/smzh.2016.57.307


 English version:
Siberian Mathematical Journal, 2016, 57:3, 470–475

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024