The bipartite Turán number and spectral extremum for linear forests

Ming Zhu Chen; Ning Wang; Long Tu Yuan; Xiao Dong Zhang

doi:10.1016/j.laa.2023.07.010

The bipartite Turán number and spectral extremum for linear forests

Ming Zhu Chen
, Ning Wang
, Long Tu Yuan
, Xiao Dong Zhang^*

^*Corresponding author for this work

School of Mathematical Sciences

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

1 Scopus citations

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=(X,Y;E) with |X|=m and |Y|=n which does not contain H as a subgraph. In this paper, we determine ex(m,n;F_ℓ) for arbitrary ℓ and appropriately large n in comparison to m and ℓ, where F_ℓ is a linear forest which consists of ℓ vertex disjoint paths. Moreover, the extremal graphs have been characterized. Furthermore, these results are used to obtain the maximum spectral radius of bipartite graphs which do not contain F_ℓ as a subgraph and characterize all extremal graphs which attain the maximum spectral radius.

Original language	English
Pages (from-to)	150-173
Number of pages	24
Journal	Linear Algebra and Its Applications
Volume	676
DOIs	https://doi.org/10.1016/j.laa.2023.07.010
State	Published - 1 Nov 2023

Keywords

Bipartite Turán number
Bipartite graph
Linear forest
Spectral radius

Access to Document

10.1016/j.laa.2023.07.010

Cite this

@article{77f44b45a81d4b5db5f265014197d8cc,

title = "The bipartite Tur{\'a}n number and spectral extremum for linear forests",

abstract = "The bipartite Tur{\'a}n number of a graph H, denoted by ex(m,n;H), is the maximum number of edges in any bipartite graph G=(X,Y;E) with |X|=m and |Y|=n which does not contain H as a subgraph. In this paper, we determine ex(m,n;Fℓ) for arbitrary ℓ and appropriately large n in comparison to m and ℓ, where Fℓ is a linear forest which consists of ℓ vertex disjoint paths. Moreover, the extremal graphs have been characterized. Furthermore, these results are used to obtain the maximum spectral radius of bipartite graphs which do not contain Fℓ as a subgraph and characterize all extremal graphs which attain the maximum spectral radius.",

keywords = "Bipartite Tur{\'a}n number, Bipartite graph, Linear forest, Spectral radius",

author = "Chen, \{Ming Zhu\} and Ning Wang and Yuan, \{Long Tu\} and Zhang, \{Xiao Dong\}",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier Inc.",

year = "2023",

month = nov,

day = "1",

doi = "10.1016/j.laa.2023.07.010",

language = "英语",

volume = "676",

pages = "150--173",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - The bipartite Turán number and spectral extremum for linear forests

AU - Chen, Ming Zhu

AU - Wang, Ning

AU - Yuan, Long Tu

AU - Zhang, Xiao Dong

PY - 2023/11/1

Y1 - 2023/11/1

N2 - 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=(X,Y;E) with |X|=m and |Y|=n which does not contain H as a subgraph. In this paper, we determine ex(m,n;Fℓ) for arbitrary ℓ and appropriately large n in comparison to m and ℓ, where Fℓ is a linear forest which consists of ℓ vertex disjoint paths. Moreover, the extremal graphs have been characterized. Furthermore, these results are used to obtain the maximum spectral radius of bipartite graphs which do not contain Fℓ as a subgraph and characterize all extremal graphs which attain the maximum spectral radius.

AB - 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=(X,Y;E) with |X|=m and |Y|=n which does not contain H as a subgraph. In this paper, we determine ex(m,n;Fℓ) for arbitrary ℓ and appropriately large n in comparison to m and ℓ, where Fℓ is a linear forest which consists of ℓ vertex disjoint paths. Moreover, the extremal graphs have been characterized. Furthermore, these results are used to obtain the maximum spectral radius of bipartite graphs which do not contain Fℓ as a subgraph and characterize all extremal graphs which attain the maximum spectral radius.

KW - Bipartite Turán number

KW - Bipartite graph

KW - Linear forest

KW - Spectral radius

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

U2 - 10.1016/j.laa.2023.07.010

DO - 10.1016/j.laa.2023.07.010

M3 - 文章

AN - SCOPUS:85165897189

SN - 0024-3795

VL - 676

SP - 150

EP - 173

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

The bipartite Turán number and spectral extremum for linear forests

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this