LA MENOR SUMA DE GRADOS Y SUCESIONES POTENCIALMENTE Pk-BIPARTITAS GRÁFICAS

Resumen

Un grafo bipartito balanceado tiene la propiedad Pk si contiene un subgrafo bipartito balanceado completo de orden 2k. Una sucesión bipartita gráfica Π =(Π_V1,Π_V2) es potencialmente Pk-bipartita gráfica si tiene una realización con la propiedad Pk. Brito et al. (2001), conjeturaron dada la menor suma de grado σ (k, 2n) tal que toda sucesión bipartita gráfica , y con y , y σ (П)≥ σ (k, 2n) es potencialmente Pk-bipartita gráfica, entonces σ (k, 2n) = 2(k-1)(2n-k) + 2k y lo demostraron para k = 2 y 3. En este artículo se demuestra la conjetura para k = 4.

PALABRAS CLAVE: Realización, bipartita, gráfica.

ABSTRACT

A balanced bipartite graph has the property Pk if it contains a complete balanced bipartite subgraph of order 2k. A graphic bipartite succession Π =(Π_V1,Π_V2) is potentially Pk- bipartite graphic if it has a realization with the property Pk. Brito et al. (2001) conjectured that given the least sum of degrees σ (k, 2n) such that all graphic bipartite succession , and with and , and σ (П) ≥ σ (k, 2n) is potentially Pk- graphic bipartite, then σ (k, 2n) = 2(k-1)(2n-k) + 2k and they demonstrated it for k = 2 and 3. In this article that conjecture is proved for k = 4.

KEY WORDS: Realization, bipartite, graphic.