RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2021, том 18, выпуск 1, страницы 456–463 (Mi semr1372)

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

All tight descriptions of major $3$-paths in $3$-polytopes without $3$-vertices

Ts. Ch.-D. Batueva, O. V. Borodin, A. O. Ivanova, D. V. Nikiforov

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia

Аннотация: A $3$-path $uvw$ is an $(i,j,k)$-path if $d(u)\le i$, $d(v)\le j$, and $d(w)\le k$, where $d(x)$ is the degree of a vertex $x$. It is well-known that each $3$-polytope has a vertex of degree at most $5$, called minor. A description of $3$-paths in a $3$-polytope is minor or major if the central item of each its triplet is at most 5 or at least $6$, respectively. Back in 1922, Franklin proved that each $3$-polytope with minimum degree 5 has a $(6,5,6)$-path, which description is tight. Recently, Borodin and Ivanova extended Franklin's theorem by producing all the ten tight minor descriptions of $3$-paths in the class $\mathbf{P_4}$ of $3$-polytopes with minimum degree at least $4$. In 2016, Borodin and Ivanova proved that each polytope with minimum degree $5$ has a $(5,6,6)$-path, and there exists no tight description of $3$-paths in this class of $3$-polytopes other than $\{(6,5,6)\}$ and $\{(5,6,6)\}$.
The purpose of this paper is to prove that there exist precisely the following four major tight descriptions of $3$-paths in $\mathbf{ P_4}$: $\{(4,9,4),(4,7,5),(5,6,6)\}$, $\{(4,9,4),(5,7,6)\}$, $\{(4,9,5),(5,6,6)\}$, and $\{(5,9,6)\}$.

Ключевые слова: plane graph, $3$-polytope, structural properties, $3$-path, tight description.

УДК: 519.172.2

MSC: 05C75

Поступила 25 марта 2021 г., опубликована 22 апреля 2021 г.

Язык публикации: английский

DOI: 10.33048/semi.2021.18.031



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


© МИАН, 2024