全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Engineering  2024 

A New Proof on the Bipartite Turán Number of Bipartite Graphs

DOI: 10.4236/eng.2024.169022, PP. 301-308

Keywords: Bipartite Turán Number, Adjacency Matrix, Zarankiewicz Problem

Full-Text   Cite this paper   Add to My Lib

Abstract:

The bipartite Turán number of a graph H, denoted by ex( m,n;H ) , is the maximum number of edges in any bipartite graph G=( A,B;E( G ) ) with | A |=m and | B |=n which does not contain H as a subgraph. When min{ m,n }>2t , the problem of determining the value of ex( m,n; K mt,nt ) 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 ex( m,n; K mt,nt ) by virtue of algebra method with the tool of adjacency matrices of bipartite graphs, which is inspired by the method using { 0,1 } -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

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133