4
$\begingroup$

Let $G$ be a planar graph, which we may assume to be a triangulation, with vertex set $V$ and edge set $E$. Suppose the minimum vertex degree is at least 3, and suppose any two distinct edges share at most one vertex.

Definition. Given an edge $e \in E$ with vertices $v_1$ and $v_2$, define $D(e) = \mathrm{deg}(v_1). \mathrm{deg}(v_2)$, the product of the degrees of the vertices of $e$.

I have been calling this quantity the density of the edge $e$, but:

Question 1: Has this quantity $D(e)$ been previously studied? Does it already have a name?

This quantity is likely to have properties akin to those of the weight $w(e) = \mathrm{deg}(v_1) + \mathrm{deg}(v_2)$. It is a result of Borodin [1] that every planar graph under consideration has a $(5,6)$ edge, a $(4,7)$ edge, a $(3,10)$ edge, or an edge with degrees less than one of these. As a direct consequence of this:

Theorem. Every planar graph $G$ has an edge $e$ with $D(e) \leq 30$.

Question 2: Is there a reference for this result?

I am interested in the values of $D$ that can and must appear in a graph with $n$ vertices.

Definition. Let $f(n)$ be the least natural number $N$ such that every planar graph with $n$ vertices has an edge $e$ with $D(e) \leq N$.

The theorem above implies that for all $n$, $f(n) \leq 30$. For example, $f(4) = 9$ because the only possible graph is the tetrahedron with all vertices degree 3, and so each edge has $D(e) = 9$. I think $f(5)=12$, $f(6)=f(7)=f(8)=16$ and $f(12)=25$. I suspect that $f(n)=30$ for all $n \geq 32$.

Question 3: Has this quantity $f(n)$ been studied for any or all $n$?

Thanks for any help.

[1] Borodin, O. V., Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps. (Russian) Diskret. Mat. 3 (1991), no. 4, 24–27.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Agreed up to $f(7)$. However, $f(8)=18$. Continuing, $f(9)=f(10)=f(11)=20$, $f(12)=25$, $f(13)=21$, $f(14)=f(15)=f(16)=f(17)=25$. It gets slower after that. $\endgroup$
    – Brendan McKay
    Commented Oct 26, 2021 at 13:21
  • 1
    $\begingroup$ These lower bounds are precise for planar graphs with minimum degree at least 4: $f(18)\ge 25$, $f(19)\ge 25$, $f(20)\ge 25$, $f(20)\ge 25$. $\endgroup$
    – Brendan McKay
    Commented Oct 26, 2021 at 13:29
  • 1
    $\begingroup$ To get $f(8)\ge 18$, start with a cube properly coloured black and white. Then join every pair of white vertices that lie on the same face. $\endgroup$
    – Brendan McKay
    Commented Oct 26, 2021 at 13:30
  • 1
    $\begingroup$ For minimum degree at least 5, the best value achieved is 25 for $21,\ldots,31$ and $f(32)\ge 30$. $\endgroup$
    – Brendan McKay
    Commented Oct 26, 2021 at 13:40
  • 1
    $\begingroup$ For $f(13)=21$, take the octahedron (6 vertices and 8 faces) and insert a new vertex of degree 3 into all but one of the faces. That gives some vertices of degree 7 adjacent to degree 3 and no smaller products. There is no planar triangulation with 13 vertices and minimum degree 5; I'm not sure what the quickest proof is. $\endgroup$
    – Brendan McKay
    Commented Oct 27, 2021 at 0:45

1 Answer 1

Reset to default
4
+100
$\begingroup$

Regarding Question 3, here is a proof that $f(n)=30$ for all $n \geq 40$. Let $H$ be a $2$-connected planar graph with minimum degree $5$. Let $G$ be obtained from $H$ by adding a new vertex inside each face of $H$, and making it adjacent to all vertices of the face. Let $V(G)=X \cup Y$, where $X=V(H)$, and $Y$ are the newly added vertices. Since $H$ has minimum degree $5$, $\deg_G(x) \geq 10$ for all $x \in X$. Moreover, $\deg_G(y) \geq 3$ for all $y \in Y$ and no two vertices of $Y$ are adjacent. Thus, $\deg(u)\deg(w) \geq 30$ for all $uw \in E(G)$. Note that $G$ is a planar graph with $|V(H)|+|F(H)|$ vertices, where $F(H)$ is the number of faces of $H$. By Euler's formula, $|V(G)|=|E(H)|+2$. Since there is a $2$-connected planar graph with minimum degree $5$ and $m$ edges for all $m \geq 38$, we are done.

Improve this answer
$\endgroup$
6
  • $\begingroup$ OK thanks. I got the stellated icosahedron and also you can do this with a dodecahedron and add a degree 5 vertex inside each face. Suspected what you say for $n>32$ but wasn't totally sure there always exists an $n$-vertex planar graph with minimum degree 5. $\endgroup$
    – Grant Lakeland
    Commented Oct 26, 2021 at 14:56
  • 1
    $\begingroup$ There is always an $n$-vertex planar graph with minimum degree 5 for all $n \geq 14$, but for the construction, we actually care about the number of edges. I updated the answer and the bound (32 became 40). $\endgroup$
    – Tony Huynh
    Commented Oct 27, 2021 at 2:17
  • 1
    $\begingroup$ (I didn't work out the details, feel free.) A dual fullerene has all vertices of degree 6 except for 12 of degree 5. They exist for $n\ge 12$ except $n=13$. Add a new vertex into each face incident with each vertex of degree 5 and at least 4 of the 6 faces incident with each vertex of degree 6. This allows a lot of freedom. $\endgroup$
    – Brendan McKay
    Commented Oct 27, 2021 at 11:25
  • $\begingroup$ OK thanks, this is helpful. Is it true that for large $n >>32$ there will exist examples with 12 degree 5 vertices, all "far apart" from each other in some sense, and $n-12$ degree 6 vertices? $\endgroup$
    – Grant Lakeland
    Commented Oct 29, 2021 at 15:07
  • $\begingroup$ @GrantLakeland If all the vertices of degree 5 are non-adjacent, those are the duals of IPR fullerenes. (IPR=independent pentagon rule, a mnemonic from chemistry). They exist for $n=32$ and all $n\ge 37$. However the construction I gave doesn't rely on non-adjacent degree 5s. The question is whether it fills the gap between 32 and Tony's general result. $\endgroup$
    – Brendan McKay
    Commented Oct 30, 2021 at 12:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .