La menor suma de grados y sucesiones potencialmente Pk-bipartitas gráficas para k = 5 | The least sum of degrees and succesions potentially Pk - bipartite graphics for k = 5

Resumen

Un grafo bipartito balanceado tiene la propiedad P_ksi contiene un subgrafo bipartito balanceado completo de orden 2k. Una sucesión bipartita gráfica Õ = (Õ_V1,Õ_V2) es potencialmente P_k-bipartita gráfica si tiene una realización con la propiedad P_k. En este artículo, a través de una investigación teórica, usando un método analítico descriptivo se demuestra, la conjetura dada por Brito et al. (2001), para k = 5 y se obtuvo el siguiente resultado. Sea G = (V₁, V₂, E) un grafo bipartito balanceado de orden 2n, si n ≥ 5, dada la menor suma de grado σ(5,2n) tal que toda sucesión bipartita gráfica Õ = (Õ_V1,Õ_V2), Õ_V1 = (a₁, a₂,..., a_n) y Õ_V2 = (b₁, b₂,..., b_n) con a₁ ≥ a₂ ≥...≥ a_n≥ 1 y b₁ ≥ b₂ ≥... ≥ b_n≥ 1, y σ(Õ) ≥ σ(5, 2n) es potencialmente P₅-bipartita gráfica, entonces σ(5,2n) = 16n-30.

Palabras clave: Realización, grafo, balanceado.

ABSTRACT

A balanced bipartite graph has the property P_kif it contains a complete balanced bipartite subgraph of order 2k. A graphic bipartite succession  Õ = (Õ_V1,Õ_V2) is potentially P_k-bipartite graphic if it has a realization with the property P_k. In this article, through a theoretical analysis, using a descriptive analytical method, the conjecture given by Brito et al. (2001), is demonstrated for k = 5 and the following result was obtained. Let  G = (V₁, V₂, E) a balanced bipartite graph of order 2n, if n ≥ 5, given the smallest sum of degree σ (5.2n) such that all bipartite graphic succession Õ = (Õ_V1,Õ_V2), Õ_V1 = (a₁, a₂,..., a_n) and Õ_V2 = (b₁, b₂,..., b_n) whit a₁ ≥ a₂ ≥...≥ a_n≥ 1 and b₁ ≥ b₂ ≥... ≥ b_n≥ 1, and σ(Õ) ≥ σ(5, 2n) is potentially P₅- graphic bipartite, then σ(5,2n) = 16n-30.

Key words: Realization, graph, balanced.