Дискретная математика и математическая кибернетика
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