Una conjetura sobre gráficas planas

Question

No sé el siguiente es un resultado conocido, pero sería muy útil para mí en mi investigación si fuera verdad.

Conjetura: Vamos a $G$ ser un plano gráfico. La suma $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} $$ es más lineal en el número de vértices.

Lo que yo sé acerca de este problema:

• Esta conjetura sería falsa si se reemplaza el mínimo, el promedio, la estrella de la gráfica es un contraejemplo, en la que la suma es cuadrática.
• Puedo probar un límite superior de $O(n \log(n))$ como sigue. Deje $A_i = \{v : 2^i \leq deg(v) < 2^{i+1}\}$, y vamos a $$ E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}. $$ Ahora, $E(G)$ es la unión de las $E_i$'s, y la contribución de un borde de $E_i$ es en la mayoría de las $2^{i+1}$. Por otro lado, como $G$ es planar el tamaño de $E_i$ es en la mayoría de las $3|\cup_{j \geq i} A_i |$. Ahora, como el grado medio en un plano gráfico es en la mayoría de los 6, el número de vértices cuyo grado es, al menos, $2^i$ es en la mayoría de las $6n/2^i$. Por lo tanto,$|E_i| \leq 18 n/ 2^i$. Tenemos $$ \sum_{\{x,y\} \in E(G)}{\min(deg(x),deg(y))} \leq \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \en 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). $$

Answer 1

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

THM. Para un simple plano gráfico con $n$ vértices, $L(G)\le 18n-36$ para $n\ge 3$.

PRUEBA. Recordemos que un simple plano gráfico con $k\ge 3$ vértices no puede tener más de $3k-6$ bordes, alcanzado por una triangulación. Deje que los grados de los vértices ser $d_1\ge d_2\ge\dots\ge d_n$. Queremos elegir $3n-6$ pares de $(v_i,w_i)$ para $v_i\lt w_i$ y lo que queremos es maximizar $\sum_i d_{w_i}$. Esto se logra presionando los pares a la izquierda tanto como sea posible, pero tenemos la restricción de que para $k\ge 3$ el número de pares de mentir en $\lbrace 1,\ldots,k\rbrace$ es en la mayoría de las $3k-6$. Así que lo mejor que podemos esperar es elegir los pares $(1,2)$, $(1,3)$ y $(2,3)$, entonces para $j\ge 4$ eligió 3 pares de $(x,j)$ para $x\lt j$. Esto le da $$ L(G) \le d_2 + 2d_3 + 3(d_4+\cdots+d_n) \le 3\sum_i d_i \le 3(6n-12).$$

El real máximos de $n=3$ a $n=18$ son: 6, 18, 30, 48, 60, 78, 93, 112, 127, 150, 162, 180, 198, 216, 234, 252, que son cómodamente dentro de los límites.

Los duales de los fullerenos muestran que la constante de 18 años pueda ser mejorado, pero la constante de 36 puede ser. Tenga en cuenta que se me cayó $3d_1+2d_2+d_3$ en el cálculo, lo que sin duda puede ser utilizado para empujar el obligado por una constante. Lo suficientemente grande como para $n$, $18n-72$ es un correcto atado y suponemos que es el valor exacto para $n\ge 13$.

Answer 2

Esto es sólo una elaboración de Brendan McKay hermosa respuesta, pero demasiado largo para un comentario. La idea crucial es simplificar el problema por la generalización de ello, la introducción de una maximización de los índices de la suma separada de la original plana gráfico de $G$.

Para $x = (x_1, \ldots, x_n) \in \mathbb{R}_{\geq 0}^n$ y un multi-gráfico de $H$ con $V(H) \subseteq \{ 1, \ldots, n \}$, vamos $$ L_H(x) := \sum_{ij \in E(H)} \min \{ x_i, x_j \} . $$ Para un número natural $d$, vamos a $\mathcal{H}_d$ ser la clase de todos los finita multi-gráficos de $H$ con $V(H) = \{ 1, \ldots, n \}$ (para cualquier $n$) tal que $e(H[A]) \leq d(|A|-1)$ mantiene para cualquier $A \subseteq V(H)$ (en otras palabras, gráficos de arboricity en la mayoría de las $d$).

Teorema: Para cualquier $x \in \mathbb{R}_{\geq 0}^n$ y cualquier $H \in \mathcal{H}_d$ tenemos $L_H(x) \leq d(\sum_{i=1}^n x_i - \max_i x_i)$.

Prueba: Podemos suponer que la $x_i >0$ es válido para cada $i$. Permutar $\{1, \ldots, n\}$, de modo que $x_1 \geq x_2 \geq \ldots \geq x_n$. Tenga en cuenta que $$ L_H(x) = \sum_{ij \in E(H) \en la cima de i \, < \, j} x_j $$

Extender la clase $\mathcal{H}_d$, ligeramente por sólo requiere que el $e(H[A]) \leq d(|A| - 1)$ tiene al $A = \{ 1, \ldots, k \}$ para algunos $k$ (es decir, $A$ es un segmento inicial de $\{ 1, \ldots, n\}$). Llame a esta nueva clase de $\mathcal{H}_d'$.

Elija $H \in \mathcal{H}_d'$ con $V(H) = \{ 1, \ldots, n \}$, de modo que $L_H(x)$ es máxima y, conforme a esto, así que $$ R(H) := \sum_{ij \in E(H)} i + j$$ es mínimo. Pretendemos que $H$ es una estrella con el centro 1. De hecho, si $ij \in E(H)$ e $1 < i < j \leq n$, entonces podríamos sustituir $ij$ por el borde de la $1j$, y obtener un gráfico de $H'$ con $L(H') = L(H)$ e $R(H') < R(H)$. Trivialmente $H' \in \mathcal{H}_d'$ así, por tanto, contradiciendo nuestra selección de $H$.

Por otra parte, todos los $j \in \{ 2, \ldots, n \}$ tiene el grado exactamente $d$ en $H$. De lo contrario, elija $j$ mínimo $d_H(j) \neq d$. Si $d_H(j) > d$, entonces para $A := \{ 1, \ldots, j \}$ tenemos $e(H[A]) > d(|A| - 1)$, una contradicción a $H \in \mathcal{H}_d'$. Por lo tanto $d_H(j) \leq d-1$. Agregar un borde a $1j$ a $H$. Si hay algo de $k > j$ con $d_H(k) > d$, tomar un mínimo de tales $k$ y eliminar una arista $1k$. Si no había ningún $k$, entonces la gráfica resultante $H'$ satisface $L(H') > L(H)$. Si había un $k$,, a continuación, $L(H') = L(H)$ e $R(H') < R(H)$. De cualquier manera, $H'$ es fácilmente visto mentir en $\mathcal{H}_d'$, por lo que contradice nuestra selección de $H$.

Ahora que $H$ se da explícitamente, se sigue que $$ L_H(x) = \sum_{j = 2}^n d x_j . $$ Esto termina la prueba.

El original de la declaración de la siguiente manera tomando como $x$ el grado de secuencia de un plano gráfico y observando que $G \in \mathcal{H}_d$ para $d = 3$.