35
$\begingroup$

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} $$ is at most linear in the number of vertices.

What I know about this problem:

  • This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
  • I can prove an upper bound of $O(n \log(n))$ as follows. Let $A_i = \{v : 2^i \leq deg(v) < 2^{i+1}\}$, and let $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Now, $E(G)$ is the union of the $E_i$'s, and the contribution of an edge from $E_i$ is at most $2^{i+1}$. On the other hand, as $G$ is planar the size of $E_i$ is at most $3|\cup_{j \geq i} A_i |$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $2^i$ is at most $6n/2^i$. Therefore $|E_i| \leq 18 n/ 2^i$. We have $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} \leq \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(deg(x),deg(y))} $$ $$ \leq\sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq \sum_{i=0}^{\log_2(n)} (18 n/ 2^i) \cdot 2^{i+1} = 36 n \log_2(n). $$
$\endgroup$
  • 1
    $\begingroup$ Just in the unlikely case that you are not aware of it and that in your work you need to know more about degree-distributions of planar graphs: it might be useful to have a look at the recent work of Drmota, Gimenez, and Noy. For example: arXiv:0911.4331v1 $\endgroup$ – Peter Heinig Jul 4 '17 at 18:26
  • 1
    $\begingroup$ Conjecture (modulo details that I do not have time to write out): if $\mathrm{L}(G)$ denotes your function, and if $\mathcal{P}_n:= \text{set of all labelled planar graphs with n vertices}$, then $\frac{1}{\lvert\mathcal{P}_n\rvert}\sum_{G\in\mathcal{P}_n}\frac{\mathrm{L}(G)}{\lvert E(G)\rvert} \sim_{n\to\infty} 4.42652 + o(1)$. $\endgroup$ – Peter Heinig Jul 4 '17 at 19:32
  • $\begingroup$ Just to summarize a bit, and to draw attention to the interesting concept of averages of higher order: it seems that the average of the average of your function (the number defined above) can more or less routinely be calculated to a precision you perhaps did not expect. For example, it seems that said second-order-average can be expressed "in terms" of elementary functions, and hence numerical approximation can be calculated to very many digits of accuracy. (But: something more complicated than "elementary functions" in the contemporary technical sense is involved.) $\endgroup$ – Peter Heinig Jul 8 '17 at 13:36
  • $\begingroup$ The "something more complicated" is the unique real solution of an equation $f(x)=0$ where $f$ in the relevant interval is a strictly monotone increasing Elementary function in the technical sense. This is perhaps getting too terminological, but: evaluating the average of the average of your function involves something like a function elementary relative to a non-algebraic equation. $\endgroup$ – Peter Heinig Jul 8 '17 at 13:44
39
$\begingroup$

Let $L(G)=\sum_{xy\in E(G)} \min\lbrace deg(x),deg(y)\rbrace$.

THM. For a simple planar graph with $n$ vertices, $L(G)\le 18n-36$ for $n\ge 3$.

PROOF. Recall that a simple planar graph with $k\ge 3$ vertices cannot have more than $3k-6$ edges, achieved by a triangulation. Let the degrees of the vertices be $d_1\ge d_2\ge\dots\ge d_n$. We want to choose $3n-6$ pairs $(v_i,w_i)$ for $v_i\lt w_i$ and we want to maximize $\sum_i d_{w_i}$. This is achieved by pushing the pairs to the left as much as possible, but we have the constraint that for $k\ge 3$ the number of pairs lying in $\lbrace 1,\ldots,k\rbrace$ is at most $3k-6$. So the best we can hope for is to chose the pairs $(1,2)$, $(1,3)$ and $(2,3)$, then for $j\ge 4$ chose 3 pairs $(x,j)$ for $x\lt j$. This gives $$ L(G) \le d_2 + 2d_3 + 3(d_4+\cdots+d_n) \le 3\sum_i d_i \le 3(6n-12).$$

The actual maximums from $n=3$ to $n=18$ are: 6, 18, 30, 48, 60, 78, 93, 112, 127, 150, 162, 180, 198, 216, 234, 252, which are comfortably within the bound.

The duals of fullerenes show that the constant 18 cannot be improved, but the constant 36 can be. Note that I dropped $3d_1+2d_2+d_3$ in the calculation, which can definitely be used to push the bound down by a constant. For large enough $n$, $18n-72$ is a correct bound and I conjecture that it is the exact value for $n\ge 13$.

$\endgroup$
  • 1
    $\begingroup$ Nice! Note that the only place that planarity is used is that every subgraph of a planar graph only has linear number of edges. So the claim is also true for every minor-closed class of graphs (with different constants). $\endgroup$ – Tony Huynh Jul 5 '17 at 17:30
  • $\begingroup$ @TonyHuynh It seems that if every subgraph has average degree at most $\Delta$, then $L(G)\le \Delta^2 n+O(1)$, and no other conditions are needed. $\endgroup$ – Brendan McKay Jul 5 '17 at 18:40
10
$\begingroup$

This is just an elaboration on Brendan McKay's beautiful answer, but too long for a comment. The crucial idea is to simplify the problem by generalising it, introducing a maximisation on the indices of the sum, detached from the original planar graph $G$.

For $x = (x_1, \ldots, x_n) \in \mathbb{R}_{\geq 0}^n$ and a multi-graph $H$ with $V(H) \subseteq \{ 1, \ldots, n \}$, let $$ L_H(x) := \sum_{ij \in E(H)} \min \{ x_i, x_j \} . $$ For a natural number $d$, let $\mathcal{H}_d$ be the class of all finite multi-graphs $H$ with $V(H) = \{ 1, \ldots, n \}$ (for any $n$) such that $e(H[A]) \leq d(|A|-1)$ holds for any $A \subseteq V(H)$ (in other words, graphs of arboricity at most $d$).

Theorem: For any $x \in \mathbb{R}_{\geq 0}^n$ and any $H \in \mathcal{H}_d$ we have $L_H(x) \leq d(\sum_{i=1}^n x_i - \max_i x_i)$.

Proof: We may assume that $x_i >0$ holds for every $i$. Permute $\{1, \ldots, n\}$ so that $x_1 \geq x_2 \geq \ldots \geq x_n$. Note that $$ L_H(x) = \sum_{ij \in E(H) \atop i \, < \, j} x_j $$

Extend the class $\mathcal{H}_d$ slightly by requiring only that $e(H[A]) \leq d(|A| - 1)$ holds when $A = \{ 1, \ldots, k \}$ for some $k$ (that is, $A$ is an initial segment of $\{ 1, \ldots, n\}$). Call this new class $\mathcal{H}_d'$.

Choose $H \in \mathcal{H}_d'$ with $V(H) = \{ 1, \ldots, n \}$ so that $L_H(x)$ is maximum and, subject to this, so that $$ R(H) := \sum_{ij \in E(H)} i + j$$ is minimum. We claim that $H$ is a star with center 1. Indeed, if $ij \in E(H)$ and $1 < i < j \leq n$, then we could replace $ij$ by the edge $1j$ and obtain a graph $H'$ with $L(H') = L(H)$ and $R(H') < R(H)$. Trivially $H' \in \mathcal{H}_d'$ as well, hence contradicting our choice of $H$.

Moreover, every $j \in \{ 2, \ldots, n \}$ has degree exactly $d$ in $H$. Otherwise, choose $j$ minimum with $d_H(j) \neq d$. If $d_H(j) > d$, then for $A := \{ 1, \ldots, j \}$ we have $e(H[A]) > d(|A| - 1)$, a contradiction to $H \in \mathcal{H}_d'$. Hence $d_H(j) \leq d-1$. Add an edge $1j$ to $H$. If there is some $k > j$ with $d_H(k) > d$, take a minimum such $k$ and delete one edge $1k$. If there was no such $k$, then the resulting graph $H'$ satisfies $L(H') > L(H)$. If there was such a $k$, then $L(H') = L(H)$ and $R(H') < R(H)$. Either way, $H'$ is easily seen to lie in $\mathcal{H}_d'$ and thus contradicts our choice of $H$.

Now that $H$ is explicitly given, it follows that $$ L_H(x) = \sum_{j = 2}^n d x_j . $$ This finishes our proof.

The original statement now follows by taking as $x$ the degree-sequence of a planar graph and noting that $G \in \mathcal{H}_d$ for $d = 3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.