Describing 4-paths in 3-polytopes with minimum degree 5

Back in 1922, Franklin proved that each 3-polytope with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol’ and Madaras (1996) ensured a 4-path with the degree-sum at most 23. The purpose of this note is to prove that each 3-polytope with minimum degree 5 has a (6, 5, 6, 6)-path or (5, 5, 5, 7)-path, which is tight and refines both above mentioned results.     

Describing 3-faces in normal plane maps with minimum degree 4

In 1940, Lebesgue proved that every 3-polytope with minimum degree at least 4 contains a 3-face for which the set of degrees of its vertices is majorized by one of the following sequences:

(4,4,∞),(4,5,19),(4,6,11),(4,7,9),(5,5,9),(5,6,7).$(4,4,\infty ),(4,5,19),(4,6,11),(4,7,9),(5,5,9),(5,6,7)\text{.}$

     

On smallest 3-polytopes of given graph radius

The 3-polytopes are planar, 3-connected graphs. A classical question is, given $r\ge 3$, is the $2(r?1)$-gonal prism $K_2\times C_{2(r?1)}$ the unique 3-polytope of graph radius r and smallest size? Under some extra assumptions, we answer this question in the positive.     

Refined weight of edges in normal plane maps

The weight $w\left(e\right)$ of an edge $e$ in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge $e=uv$ is of type $(i,j)$ if $d\left(u\right)\le i$ and $d\left(v\right)\le j$. In 1940, Lebesgue proved that every NPM has an edge of one of the types $(3,11)$, $(4,7)$, or $(5,6)$, where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-connected planar graph has an edge $e$ with $w\left(e\right)\le 13$, which bound is sharp. Borodin (1989), answering Erd?s’ question, proved that every NPM has either a $(3,10)$-edge, or $(4,7)$-edge, or $(5,6)$-edge.A vertex is simplicial if it is completely surrounded by 3-faces. In 2010, Ferencová and Madaras conjectured (in different terms) that every 3-polytope without simplicial 3-vertices has an edge $e$ with $w\left(e\right)\le 12$. Recently, we confirmed this conjecture by proving that every NPM has either a simplicial 3-vertex adjacent to a vertex of degree at most 10, or an edge of types $(3,9)$, $(4,7)$, or $(5,6)$.By a $k^{\left(?\right)}$-vertex we mean a $k$-vertex incident with precisely $?$ triangular faces. The purpose of our paper is to prove that every NPM has an edge of one of the following types: $(3^{\left(3\right)},10)$, $(3^{\left(2\right)},9)$, $(3^{\left(1\right)},7)$, $(4^{\left(4\right)},7)$, $(4^{\left(3\right)},6)$, $(5^{\left(5\right)},6)$, or $(5,5)$, where all bounds are best possible. In particular, this implies that the bounds in $(3,10)$, $(4,7)$, and $(5,6)$ can be attained only at NPMs having a simplicial 3-, 4-, or 5-vertex, respectively.     

3-Vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices

Let $g(k,t)$ be the minimum integer such that every plane graph with girth g at least $g(k,t)$, minimum degree $\delta =2$ and no $(k+1)$-paths consisting of vertices of degree 2, where $k\ge 1$, has a 3-vertex with at least t neighbors of degree 2, where $1\le t\le 3$.In 2015, Jendrol' and Maceková proved $g(1,1)\le 7$. Later on, Hudák et al. established $g(1,3)=10$, Jendrol', Maceková, Montassier, and Soták proved $g(1,1)\ge 7$, $g(1,2)=8$ and $g(2,2)\ge 11$, and we recently proved that $g(2,2)=11$ and $g(2,3)=14$.Thus $g(k,t)$ is already known for $k=1$ and all t. In this paper, we prove that $g(k,1)=3k+4$, $g(k,2)=3k+5$, and $g(k,3)=3k+8$ whenever $k\ge 2$.     

Almost all 5-regular graphs have a 3-flow

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.     

Low minor faces in 3-polytopes

It is trivial that every 3-polytope has a face of degree at most 5, called minor. The height $h\left(f\right)$ of a face $f$ is the maximum degree of the vertices incident with $f$. It follows from the partial double $n$-pyramids that $h\left(f\right)$ can be arbitrarily large for each $f$ if a 3-polytope is allowed to have faces of types $(4,4,\infty )$ or $(3,3,3,\infty )$.In 1996, M. Horňák and S. Jendrol’ proved that every 3-polytope without faces of types $(4,4,\infty )$ and$(3,3,3,\infty )$ has a minor face of height at most 39 and constructed such a 3-polytope satisfying $h\left(f\right)\ge 30$ for all minor faces $f$.The purpose of this paper is to prove that every 3-polytope without faces of types $(4,4,\infty )$ and$(3,3,3,\infty )$ has a minor face of height at most 30, which bound is tight due to the Horňák–Jendrol’ construction.     

Generating quadrangulations of surfaces with minimum degree at least 3

In this article, we show that all quadrangulations of the sphere with minimum degree at least 3 can be constructed from the pseudo‐double wheels, preserving the minimum degree at least 3, by a sequence of two kinds of transformations called “vertex‐splitting” and “4‐cycle addition.” We also consider such generating theorems for other closed surfaces. These theorems can be translated into those of 4‐regular graphs on surfaces by taking duals. © 1999 John Wiley & Sons, In. J Graph Theory 30: 223–234, 1999     

The number of vertices of degree 5 in a contraction-critically 5-connected graph

An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V₅(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {G_i} such that lim_i→∞|V₅(G_i)|/|V(G_i)|=1/2.     

Reductions of 3-connected graphs with minimum degree at least four

We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x₁, x₂, x₃, x₄} and x₁x₂, x₃x₄ ∈ E(G) such that the graph (G ? x)/x₁x₂/x₃x₄ obtained by contraction of edges x₁x₂ and x₃x₄ in G – x is a 3-connected graph of minimum degree at least 4.

Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions.     

3-trees with few vertices of degree 3 in circuit graphs

A circuit graph(G,C) is a 2-connected plane graph G with an outer cycle C such that from each inner vertex v, there are three disjoint paths to C. In this paper, we shall show that a circuit graph with n vertices has a 3-tree (i.e., a spanning tree with maximum degree at most 3) with at most vertices of degree 3. Our estimation for the number of vertices of degree 3 is sharp. Using this result, we prove that a 3-connected graph with n vertices on a surface F_χ with Euler characteristic χ≥0 has a 3-tree with at most vertices of degree 3, where c_χ is a constant depending only on F_χ.