Plaza libre gráfico : Gráficos con un mínimo de duración de un ciclo mayor que 4.
Pregunta : ¿Cuál es el máximo número de aristas posibles para una plaza libre gráfico de $G(V,E)$ que $|V|$ = n. Es de la orden de $O(n^2)$?
¿Cómo funciona la respuesta cambio si max_degree(G) = d ($>1$)?
EDIT: por curiosidad, ¿cuál es el máximo número de aristas con $n$ vértices, cuando nos limitamos a la circunferencia de la gráfica de $l$.
Gracias de antemano!
Según el Resumen (postscript), Zoltan Füredi demuestra que para $q \ge 25$ $C_4$libre de gráfico en $q^2 + q + 1$ vértices tiene en la mayoría de las $\frac{1}{2}q(q+1)^2$ bordes, lo que implica $\frac{1}{2}n^{3/2}$ máximo bordes asintóticamente (para $n$ nodos). Füredi también describe los gráficos que alcancen su límite superior en términos finitos planos proyectivos. [NOTA: Después de ver el documento en sí y las referencias a la misma, la correcta límite superior es $\frac{1}{2}q(q+1)^2$ bordes, en ligera variación con el Resumen.]
Sus papeles están disponibles en PDF y PS descargar en este enlace, artículo 148., que incluye algunos más (publicados y no publicados) versiones.
El número máximo de aristas en cualquier finito simple gráfico es de la orden de $O(n^2)$, por lo que su conjetura es verdadera, supongo, pero trivialmente.
De todos modos, su pregunta se encuentra en el área de "extremal la teoría de grafos." Hay un libro de Bollobás con ese título que no he leído pero probablemente sería un buen lugar para empezar. También hay un capítulo en Diestel del libro que puede ser útil para usted.
En cuanto a tu pregunta en concreto, una rápida búsqueda en google encontrado el siguiente documento: "Extremal gráficos de la circunferencia de 5" por Garnick, Kwong y Lazebnik
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
