Relación entre el número de aristas del grafo y la capacidad de cobertura

Question

Sea $G$ sea un grafo conexo en $n$ nodos, $m$ bordes. Un grafo es $(b, r)$ cubierto si puede ser cubierto por $b$ bolas de radio $r$ (en otras palabras, existe un conjunto de $b$ nodos tales que todos los nodos estén a una distancia $r$ de uno de estos $b$ nodos). Supongamos que $G$ es $(b, r)$ Cubrible.

Intuitivamente, siento que debería haber una buena relación entre $m, b,$ y $r$ . Por ejemplo, si $m$ se fija en su valor mínimo ( $n-1$ ), entonces tenemos la relación $b(2r+1) \ge n$ (porque los nodos están dispuestos en una gran cadena). Alternativamente, si $m$ se fija en su valor máximo ( $n(n-1)$ ), entonces $G$ es el grafo completo y es trivialmente $(1, 1)$ Cubrible.

¿Existe algún límite de la forma $f(b, r, m) \ge g(n, m)$ que generalice estos ejemplos?

Answer 1

Si su gráfico es $k$ -regular, entonces se puede aproximar el diámetro con $log_{k}(n)$ . Sea $\delta(G) := min \{ d(v) : v \in V(G) \}$ . Puede acotar el diámetro anterior mediante $\lceil log_{\delta(G)}(n) \rceil$ . Del mismo modo, dejemos que $\Delta(G)$ es el grado máximo del grafo, y se puede utilizar para obtener un límite inferior del diámetro. Asegúrate de poner el límite inferior en el suelo.