EXTREMAL GRAPHS FOR EVEN LINEAR FORESTS IN BIPARTITE GRAPHS

Long Tu Yuan; Xiao Dong Zhang

doi:10.7151/dmgt.2429

EXTREMAL GRAPHS FOR EVEN LINEAR FORESTS IN BIPARTITE GRAPHS

Long Tu Yuan, Xiao Dong Zhang

School of Mathematical Sciences

Shanghai Jiao Tong University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

Zarankiewicz proposed the problem of determining the maximum number of edges in an (n, m)-bipartite graph containing no complete bipartite graph K_a,b. In this paper, we consider a variant of the Zarankiewicz problem and determine the maximum number of edges of an (n, m)-bipartite graph without containing a linear forest consisting of even paths. Moveover, all these extremal graphs are characterized in a recursion way.

Original language	English
Pages (from-to)	5-16
Number of pages	12
Journal	Discussiones Mathematicae - Graph Theory
Volume	44
Issue number	1
DOIs	https://doi.org/10.7151/dmgt.2429
State	Published - 2024

Keywords

Turán number
bipartite graph
extremal graph
linear forest

Access to Document

10.7151/dmgt.2429

Cite this

@article{286db15081e44c89afb1e878a2a57040,

title = "EXTREMAL GRAPHS FOR EVEN LINEAR FORESTS IN BIPARTITE GRAPHS",

abstract = "Zarankiewicz proposed the problem of determining the maximum number of edges in an (n, m)-bipartite graph containing no complete bipartite graph Ka,b. In this paper, we consider a variant of the Zarankiewicz problem and determine the maximum number of edges of an (n, m)-bipartite graph without containing a linear forest consisting of even paths. Moveover, all these extremal graphs are characterized in a recursion way.",

keywords = "Tur{\'a}n number, bipartite graph, extremal graph, linear forest",

author = "Yuan, \{Long Tu\} and Zhang, \{Xiao Dong\}",

year = "2024",

doi = "10.7151/dmgt.2429",

language = "英语",

volume = "44",

pages = "5--16",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

TY - JOUR

T1 - EXTREMAL GRAPHS FOR EVEN LINEAR FORESTS IN BIPARTITE GRAPHS

AU - Yuan, Long Tu

AU - Zhang, Xiao Dong

PY - 2024

Y1 - 2024

N2 - Zarankiewicz proposed the problem of determining the maximum number of edges in an (n, m)-bipartite graph containing no complete bipartite graph Ka,b. In this paper, we consider a variant of the Zarankiewicz problem and determine the maximum number of edges of an (n, m)-bipartite graph without containing a linear forest consisting of even paths. Moveover, all these extremal graphs are characterized in a recursion way.

AB - Zarankiewicz proposed the problem of determining the maximum number of edges in an (n, m)-bipartite graph containing no complete bipartite graph Ka,b. In this paper, we consider a variant of the Zarankiewicz problem and determine the maximum number of edges of an (n, m)-bipartite graph without containing a linear forest consisting of even paths. Moveover, all these extremal graphs are characterized in a recursion way.

KW - Turán number

KW - bipartite graph

KW - extremal graph

KW - linear forest

UR - https://www.scopus.com/pages/publications/85117228201

U2 - 10.7151/dmgt.2429

DO - 10.7151/dmgt.2429

M3 - 文章

AN - SCOPUS:85117228201

SN - 1234-3099

VL - 44

SP - 5

EP - 16

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 1

ER -

EXTREMAL GRAPHS FOR EVEN LINEAR FORESTS IN BIPARTITE GRAPHS

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this