The bipartite Turán number of a graph H, denoted by
, is the maximum number of edges in any bipartite graph
with
and
which does not contain H as a subgraph. When
, the problem of determining the value of
has been solved by Balbuena et al. in 2007, whose proof focuses on the structural analysis of bipartite graphs. In this paper, we provide a new proof on the value of
by virtue of algebra method with the tool of adjacency matrices of bipartite graphs, which is inspired by the method using
-matrices due to Zarankiewicz [Problem P 101. Colloquium Mathematicum, 2(1951), 301].
References
[1]
Turán, P. (1941) On an Extremal Problem in Graph Theory. Matematikai eś Fizikai Lapok, 48, 436-452.
[2]
Erdős, P. and Simonovits, M. (1966) A Limit Theorem in Graph Theory. Studia Scientiarum Mathematicarum Hungarica, 1, 51-57.
[3]
Erdős, P. and Stone, A.H. (1946) On the Structure of Linear Graphs. Bulletin of the American Mathematical Society, 52, 1087-1091.
[4]
Kóvari, T., Sós, V. and Turán, P. (1954) On a Problem of K. Zarankiewicz. Colloquium Mathematicum, 3, 50-57. https://doi.org/10.4064/cm-3-1-50-57
[5]
Erdős, P. (1966) Some Recent Results on Extremal Problems in Graph Theory (Results). In: Theory of Graphs, 117-123.
[6]
Alon, N., Rónyai, L. and Szabó, T. (1999) Norm-Graphs: Variations and Applications. Journal of Combinatorial Theory, Series B, 76, 280-290. https://doi.org/10.1006/jctb.1999.1906
[7]
Kollár, J., Rónyai, L. and Szabó, T. (1996) Norm-Graphs and Bipartite Turán Numbers. Combinatorica, 16, 399-406. https://doi.org/10.1007/bf01261323
[8]
Füredi, Z. (1991) On a Turán Type Problem of Erdős. Combinatorica, 11, 75-79. https://doi.org/10.1007/bf01375476
[9]
Alon, N., Krivelevich, M. and Sudakov, B. (2003) Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions. Combinatorics, Probability and Computing, 12, 477-494. https://doi.org/10.1017/s0963548303005741
[10]
Gyárfás, A., Rousseau, C.C. and Schelp, R.H. (1984) An Extremal Problem for Paths in Bipartite Graphs. Journal of Graph Theory, 8, 83-95. https://doi.org/10.1002/jgt.3190080109
[11]
Li, X., Tu, J. and Jin, Z. (2009) Bipartite Rainbow Numbers of Matchings. Discrete Mathematics, 309, 2575-2578. https://doi.org/10.1016/j.disc.2008.05.011
[12]
Erdös, P., Sárközy, A. and Sós, V.T. (1995) On Product Representations of Powers, I. European Journal of Combinatorics, 16, 567-588. https://doi.org/10.1016/0195-6698(95)90039-x
[13]
N. Sárközy, G. (1995) Cycles in Bipartite Graphs and an Application in Number Theory. Journal of Graph Theory, 19, 323-331. https://doi.org/10.1002/jgt.3190190305
[14]
Györi, E. (1997) C6-Free Bipartite Graphs and Product Representation of Squares. Discrete Mathematics, 165, 371-375. https://doi.org/10.1016/s0012-365x(96)00184-7
[15]
Győri, E. (2006) Triangle-Free Hypergraphs. Combinatorics, Probability and Computing, 15, 185-191. https://doi.org/10.1017/s0963548305007108
[16]
Balbuena, C., García-Vázquez, P., Marcote, X. and Valenzuela, J.C. (2007) Counterexample to a Conjecture of Györi on C2l-Free Bipartite Graphs. Discrete Mathematics, 307, 748-749. https://doi.org/10.1016/j.disc.2006.07.003
[17]
Li, B. and Ning, B. (2021) Exact Bipartite Turán Numbers of Large Even Cycles. Journal of Graph Theory, 97, 642-656. https://doi.org/10.1002/jgt.22676
[18]
Jackson, B. (1985) Long Cycles in Bipartite Graphs. Journal of Combinatorial Theory, Series B, 38, 118-131. https://doi.org/10.1016/0095-8956(85)90077-2
[19]
Zarankiewicz, K. (1951) Problem P 101. Colloquium Mathematicum, 2, 301.
[20]
Goddard, W., Henning, M.A. and Oellermann, O.R. (2000) Bipartite Ramsey Numbers and Zarankiewicz Numbers. Discrete Mathematics, 219, 85-95. https://doi.org/10.1016/s0012-365x(99)00370-2
[21]
Griggs, J.R. and Ouyang, J. (1997) (0,1)-Matrices with No Half-Half Submatrix of Ones. European Journal of Combinatorics, 18, 751-761. https://doi.org/10.1006/eujc.1996.0133
[22]
Balbuena, C., García-Vázquez, P., Marcote, X. and Valenzuela, J.C. (2007) New Results on the Zarankiewicz Problem. Discrete Mathematics, 307, 2322-2327. https://doi.org/10.1016/j.disc.2006.11.002
[23]
Yang, Y. (2018) The Signless Laplacian Spectral Radius of Some Special Bipartite Graphs. Journal of Applied Mathematics and Physics, 6, 2159-2165. https://doi.org/10.4236/jamp.2018.610181
[24]
Wang, G. and Liu, G. (2012) Rainbow Matchings in Properly Colored Bipartite Graphs. Open Journal of Discrete Mathematics, 2, 62-64. https://doi.org/10.4236/ojdm.2012.22011