Dejemos que $G$ sea un grafo con el mismo número de vértices y aristas y grado máximo de 3.
Por razones que explicaré, creo que una cubierta de vértices mínima tiene un tamaño máximo de $\frac{2}{3} |E(G)|$ .
Es muy posible que me equivoque y si tienes un contraejemplo, ¡eso lo resolverá!
Obsérvese que G no es necesariamente conexo, de lo contrario tenemos $\tau (G) \leq \frac{1}{2} (|E(G)|+1)$ y esto resuelve el problema.
Mi intuición proviene de las siguientes observaciones:
Si todos los vértices son de grado $2$ entonces el peor caso es si el gráfico es sólo un conjunto de triángulos, entonces tenemos exactamente $\tau (G) = \frac{2}{3} |E(G)|$ .
Si no hay ninguna arista en el gráfico, los resultados se mantienen. (Todo grafo conexo de tamaño mínimo 4 tiene $\tau (G) \leq \frac{2}{3} |E(G)|$ )
Si hay una sola arista, entonces tenemos dos vértices de grado $1$ y también dos vértices de grado $3$ . Esos dos vértices de grado $3$ debería ayudar a mantener la cobertura mínima de vértices por debajo de un determinado límite (esta es la parte de la intuición).
He intentado crear algunos casos malos con gráficos que contienen aristas simples. Creo que uno de los peores casos es si el gráfico tiene 2 aristas simples y un K4. Entonces $|E(G)|=|V(G)|=8$ y $\tau (G)= \frac{5}{8} |E(G)|$ el resultado sigue siendo válido.
Nunca he trabajado en la cobertura de vértices, así que probablemente me estoy perdiendo algunos resultados importantes que ayudarían a resolver este problema. Además, mi intuición en esta área es probablemente un poco débil.
Muchas gracias
