Gráficos más grandes de circunferencia al menos 6

Question

Sea $e_6(n)$ sea el mayor número de aristas de un grafo simple con $n$ vértices y una circunferencia de al menos 6. Sea $G_6(n)$ sea el conjunto de grafos simples de orden $n$ con una circunferencia de al menos 6 y $e_6(n)$ bordes.

Mi pregunta: ¿Hay alguna $n$ para el que ninguno de los gráficos de $G_6(n)$ ¿es bipartito?

A partir de experimentos informáticos, he descubierto que los únicos valores de $n\le 50$ para lo cual $G_6(n)$ tiene algún gráfico no bipartito son 7 (7 aristas), 9 (10 aristas), 15 (22 aristas), 27 (53 aristas) y 43 (106 aristas). Sin embargo, en todos estos casos $G_6(n)$ incluye también los grafos bipartitos.

Una mesa (hay que comprobarlo, por favor, no cite todavía ): "[n=44,e=108,g=12]" significa $e_6(44)=108$ y hay 12 gráficos. Todos los grafos son bipartitos a menos que la notación sea como "[n=15,e=22,g=2+1]", lo que significa que hay dos grafos bipartitos y uno no bipartito.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11, e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17, e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23, e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29, e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77, g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100, g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47, e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

Actualización Nov 2015 : Para $51\le n\le 63$ todos los grafos extremos son bipartitos excepto $n=63$ donde hay 3 grafos extremos bipartitos y 4 grafos extremos no bipartitos (187 aristas).

Answer 1

Estoy recopilando algunas reflexiones variadas sobre el problema, con la esperanza de que sirvan de inspiración para que alguien lo termine.

Antes sugerí que los gráficos de $G_{n+1}$ podría construirse de forma incremental a partir de gráficos en $G_n$ añadiendo un vértice y el número apropiado de aristas. Brendan McKay me aseguró que esto no sería posible para $n=44$ como "ese grafo tenía demasiadas aristas", para reinterpretar su seguridad. Aun así, podría ser útil considerar la relación de subgrafos sobre la unión de los $G$ y ver si la mayoría de ellos se pueden construir de forma incremental, y caracterizar los que no lo son y son primitivos en algún sentido.

Está claro que eliminar un vértice y sus aristas adyacentes de un ejemplo en $G_{n+1}$ no reduce la circunferencia mínima, y que añadir un vértice y una sola arista tampoco reduce la circunferencia, por lo que la función $e(n)$ está aumentando en $n$ para $n>4$ y además aumenta en no más que el grado mínimo tomado sobre todos los vértices de todos los miembros de $G_{n+1}$ .

Es probable que exista un buen argumento que limite el grado máximo entre todos los miembros de $G_n$ pero no lo veo. Puedo construir un grafo con un número par de vértices pegando un número de caminos de longitud 3 en sus extremos, pero esto da un grado medio ligeramente inferior a 3 y un grado máximo ligeramente inferior a n/2, por lo que es más útil para proporcionar un límite inferior para $e(n)$ que cualquier otra cosa.

Otra construcción que da un bipartito consiste en asociar cada punto de un conjunto L con un pequeño subconjunto (de tamaño 3, digamos) de otro conjunto R de forma que ningún subconjunto de R así elegido se cruce en más de un punto. El resultado tiene una circunferencia de 6 o más y si tanto L como R tienen 7 puntos, un ejemplo máximo se parece a un BIBD (o para mí, una matriz de adyacencia de 0 y 1 con orden 7 y valor determinante absoluto de 24) que creo que corresponde al ejemplo de Brendan para $n=14$ . ¿Quizás los BIBD aporten más ejemplos? Podrían ser una subclase significativa de los grafos primitivos en la relación de subgrafos que menciono más arriba.

Además, ¿por qué tantos gráficos para $n=45$ ? Me hace pensar en la explosión combinatoria de clases de equivalencia de matrices de Hadamard, aunque sería mejor pensar en clases de equivalencia (bajo permutaciones de filas y columnas y quizá también bajo conmutación) de matrices 0-1 que tengan valores determinantes máximos. ¿Existen análogos combinatorios en la literatura que puedan sugerir esta breve plétora de ejemplos?

Gerhard "Binary Matrices On My Mind" Paseman, 2012.06.28

Answer 2

Parece que tengo una respuesta a mi propia pregunta, aunque el mérito es de mi ordenador. A saber, $e_6(47)=118$ y el único grafo de esa clase no es bipartito. Me gustaría poder ofrecer alguna pista, pero por el momento es un misterio.

Lo siento mucho, era incorrecto. Debo haber estado mirando el archivo equivocado. Hasta el $n=48$ vértices inclusive siempre hay al menos un grafo bipartito con $e_6(n)$ bordes. Así que el problema sigue abierto.