La menor suma de grados que conduce a sucesiones potencialmente Pk- bipartitas gráficas

Abstract

Un grafo bipartito balanceado tiene la propiedad Pk si contiene un subgrafo bipartito balanceado completo de orden 2k, y una sucesión ?= (?x, ?y) es potencialmente Pk - bipartita gráfica si tiene una realización con la propiedad Pk· Sea ?(k, 2n) la menor suma de grados tal que toda sucesión bipartita gráfica ? de 2n términos sin ceros y con suma de grados ?(?) ? ?(k, 2n) es potencialmente Pk - bipartita gráfica. En este artículo se conjetura que ?(k, 2n) = 2(k- 1)(2n- k)+ 2k, y se prueba que esto es cierto para k = 2 y 3.