2021Journal of Graph TheoryRequires access

Exact bipartite Turán numbers of large even cycles

Binlong Li, Bo Ning

Open publisher page 9 citations

Abstract

Abstract The bipartite Turán number, denoted by , is the maximum number of edges in an ‐free bipartite graph with two parts of sizes and , respectively. In this article, we prove for any positive integers with , which confirms (in a strong form) the unsolved case of a conjecture of Győri. Let be a bipartite graph with and . Suppose that for some . We prove that contains cycles of all even lengths from 4 to if . This result sharpens a theorem on long cycles in bipartite graphs due to Jackson. As a main tool, for a longest cycle in a bipartite graph, we prove an upper bound of the number of edges which are incident with at most one vertex in , which is a bipartite analogue of a classical theorem of Bondy. Our proof technique is structural.

About this research paper

What this paper is about

Abstract The bipartite Turán number, denoted by , is the maximum number of edges in an ‐free bipartite graph with two parts of sizes and , respectively. In this article, we prove for any positive integers with , which confirms (in a strong form) the unsolved case of a conjecture of Győri. Let be a bipartite graph with and . Suppose that for some . We prove that contains cycles of all even lengths from 4 to if . This result sharpens a theorem on long cycles in bipartite graphs due to Jackson. As a main tool, for a longest cycle in a bipartite graph, we prove an upper bound of the number of edges which are incident with at most one vertex in , which is a bipartite analogue of a classical theorem of Bondy. Our proof technique is structural.

Why it matters

OpenAlex reports 9 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Abstract The bipartite Turán number, denoted by , is the maximum number of edges in an ‐free bipartite graph with two parts of sizes and , respectively. In this article, we prove for any positive integers with , which confirms (in a strong form) the unsolved case of a conjecture of Győri. Let be a bipartite graph with and . Suppose that for some . We prove that contains cycles of all even lengths from 4 to if . This result sharpens a theorem on long cycles in bipartite graphs due to Jackson. As a main tool, for a longest cycle in a bipartite graph, we prove an upper bound of the number of edges which are incident with at most one vertex in , which is a bipartite analogue of a classical theorem of Bondy. Our proof technique is structural.

Key concepts: Bipartite graph, Combinatorics, Mathematics, Complete bipartite graph, Conjecture, Edge-transitive graph, Vertex (graph theory), Graph

Related papers

Back to paper searchBrowse research topicsOriginal source
Exact bipartite Turán numbers of large even cycles — Research Paper | ScholarLens