Search

Over the last several decades, much research has been devoted to structural and coloring problems on the plane graphs that are sparse in some sense. In this paper we deal with the densest instances of sparse 3-polytopes, namely, those without adjacent 3-cycles. Borodin proved in 1996 that such 3-polytope has a vertex of degree at most 4 and, moreover, an edge with the degree-sum of its end-vertices at most 9, where both bounds are sharp. Denote the degree of a vertex by . An edge in a 3-polytope is an -edge if and . The well-known (3,5;4,4)-Archimedean solid corresponds to a plane quadrangulation in which every edge joins a 3-vertex with a 5-vertex. In particular, this 3-polytope has no 3-cycles. Recently, Borodin and Ivanova proved that every 3-polytope with neither adjacent 3-cycles nor -edges has a 3-face with the degree-sum of its incident vertices (weight) at most 16, which bound is sharp. A 3-face is an -face or a face of type if , , and . The purpose of this paper is to prove that there are precisely two tight descriptions of 3-face-types in 3-polytopes without adjacent 3-cycles under the above-mentioned necessary assumption of the absence of -edges; namely, and . This implies that there is a unique tight description of 3-faces in 3-polytopes with neither adjacent 3-cycles nor 3-vertices: . [ABSTRACT FROM AUTHOR]

The height h( f) of a face f in a 3-polytope is the maximum of the degrees of vertices incident with f. A 4-face is pyramidal if it is incident with at least three 3-vertices. We note that in the (3, 3, 3, n)-Archimedean solid each face f is pyramidal and satisfies h( f) = n. In 1940, Lebesgue proved that every quadrangulated 3-polytope without pyramidal faces has a face f with h( f) ≤ 11. In 1995, this bound was improved to 10 by Avgustinovich and Borodin. Recently, the authors improved it to 8 and constructed a quadrangulated 3-polytope without pyramidal faces satisfying h( f) ≥ 8 for each f. The purpose of this paper is to prove that each 3-polytope without triangles and pyramidal 4-faces has either a 4-face with h( f) ≤ 10 or a 5-face with h( f) ≤ 5, where the bounds 10 and 5 are sharp. [ABSTRACT FROM AUTHOR]

Each 3-polytope has obviously a face of degree at most 5 which is called minor. The height of is the maximum degree of the vertices incident with . A type of a face is defined by a set of upper constraints on the degrees of vertices incident with . This follows from the double -pyramid and semiregular -polytope, can be arbitrarily large for each if a 3-polytope is allowed to have faces of types or which are called pyramidal. Denote the minimum height of minor faces in a given 3-polytope by . In 1996, Horňák and Jendrol' proved that every 3-polytope without pyramidal faces satisfies and constructed a 3-polytope with . In 2018, we proved the sharp bound . In 1998, Borodin and Loparev proved that every 3-polytope with neither pyramidal faces nor -faces has a face such that if , or if , or if , where bounds 20 and 5 are best possible. We prove that every 3-polytope with neither pyramidal faces nor -faces has with if , or if , or if , where all bounds 20, 10, and 5 are best possible. [ABSTRACT FROM AUTHOR]

The authors study the class of finite homogeneous metric spaces and some of its important subclasses that have natural definitions in terms of the metrics and well-studied analogs in the class of Riemannian manifolds. The relationships between these classes are explored. The examples of the corresponding spaces are built, some of which are the vertex sets of the special convex polytopes in Euclidean space. We describe the classes on using the language of graph theory, which enables us to provide some examples of finite metric spaces with unusual properties. Several unsolved problems are posed. [ABSTRACT FROM AUTHOR]

Attempting to solve the Four Color Problem in 1940, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P5. Given a 3-polytope P, by w(P) denote the minimum of the maximum degree-sum (weight) of the neighborhoods of 5-vertices (minor 5-stars) in P. In 1996, Jendrol' and Madaras showed that if a polytope P in P5 is allowed to have a 5-vertex adjacent to four 5-vertices (called a minor (5, 5, 5, 5, ∞)-star), then w(P) can be arbitrarily large. For each P* in P5 with neither vertices of degree 6 and 7 nor minor (5, 5, 5, 5, ∞)-star, it follows from Lebesgue's Theorem that w(P*) ≤ 51. We prove that every such polytope P* satisfies w(P*) ≤ 42, which bound is sharp. This result is also best possible in the sense that if 6-vertices are allowed but 7-vertices forbidden, or vice versa; then the weight of all minor 5-stars in P5 under the absence of minor (5, 5, 5, 5, ∞)-stars can reach 43 or 44, respectively. [ABSTRACT FROM AUTHOR]

In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. Very few precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P . Given a 3-polytope P, denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P by h( P). Jendrol' and Madaras in 1996 showed that if a polytope P in P is allowed to have a 5-vertex adjacent to four 5-vertices (called a minor (5, 5, 5, 5,∞)- star), then h( P) can be arbitrarily large. For each P in P with neither vertices of the degree from 6 to 8 nor minor (5, 5, 5, 5,∞)-star, it follows from Lebesgue's Theorem that h( P ) ≤ 17. We prove in particular that every such polytope P satisfies h( P ) ≤ 12, and this bound is sharp. This result is best possible in the sense that if vertices of one of degrees in {6, 7, 8} are allowed but those of the other two forbidden, then the height of minor 5-stars in P under the absence of minor (5, 5, 5, 5,∞)- stars can reach 15, 17, or 14, respectively. [ABSTRACT FROM AUTHOR]