Deje $G = (V, E)$ estar conectada, grafo, y no bipartito gráfico. ¿Cuál es la máxima longitud de la menor impar ciclo?
Estoy trabajando en un algoritmo para calcular el bipartivity grado. Véase, por ejemplo, la sección 7.2 de la Caracterización de Redes Complejas: Una Encuesta de las mediciones. Mi algoritmo es similar en algunos aspectos a subgrafo centralidad, pero no es una espectral algoritmo; es decir, que no se expresa en términos de los valores propios o vectores propios de la matriz de adyacencia del grafo. En lugar de eso, me parece ciertos tipos de cerrado de las caminatas de la longitud de la $1 \ldots k$. Por lo tanto, si hay una conocida límite superior de la longitud de la menor impar ciclo en un no-bipartita gráfica, entonces yo puedo saber cuán grande $k$ debe estar en orden para capturar cierta información acerca de cómo lejos de ser bipartito no grafo es bipartito.
