• Title of article

    Extremal -free bipartite graphs

  • Author/Authors

    Valenzuela، نويسنده , , J.C. and Balbuena، نويسنده , , C. and Garc?a–V?zquez، نويسنده , , P. and Marcote، نويسنده , , X.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2006
  • Pages
    6
  • From page
    139
  • To page
    144
  • Abstract
    We approach a well-known topic in extremal graph theory, the so-called Zarankiewicz Problem [K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951), 301], which consists in: (i) calculating the maximum number of edges z ( m , n ; s , t ) that a bipartite graph G with partite classes of cardinalities m and n can have such that G is free of a complete bipartite subgraph K ( s , t ) with s vertices in the m class and t vertices in the n class; (ii) describing all the corresponding extremal bipartite graphs having that maximum number of edges. In this paper, the exact value of z ( m , n ; s , t ) is calculated and the corresponding family Z ( m , n ; s , t ) of extremal graphs is characterized when the parameters satisfy certain relationships.
  • Keywords
    Forbidden subgraphs , Extremal graph , Zarankiewicz problem
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Serial Year
    2006
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Record number

    1454432