RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2021 Volume 18, Issue 1, Pages 456–463 (Mi semr1372)

Discrete mathematics and mathematical cybernetics

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

Abstract: 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)\}$.

Keywords: plane graph, $3$-polytope, structural properties, $3$-path, tight description.

UDC: 519.172.2

MSC: 05C75

Received March 25, 2021, published April 22, 2021

Language: English

DOI: 10.33048/semi.2021.18.031



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024