Counterexamples of the Bhattacharya-Friedland-Peled conjecture

Yen Jen Cheng; Chia An Liu; Chih wen Weng

doi:10.1016/j.laa.2022.02.020

Counterexamples of the Bhattacharya-Friedland-Peled conjecture

Yen Jen Cheng, Chia An Liu^*, Chih wen Weng

^*Corresponding author for this work

Degree Program of Science

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

Abstract

The Brualdi-Hoffman conjecture, proved by Rowlinson in 1988, characterized the graph with maximal spectral radius among all simple graphs with prescribed number of edges. In 2008, Bhattacharya, Friedland, and Peled proposed an analog, which will be called the BFP conjecture in the following, of the Brualdi-Hoffman conjecture for the bipartite graphs with fixed numbers of edges in the graph and vertices in the bipartition. The BFP conjecture was proved to be correct if the number of edges is large enough by several authors. However, in this paper we provide some counterexamples of the BFP conjecture.

Original language	English
Pages (from-to)	200-207
Number of pages	8
Journal	Linear Algebra and Its Applications
Volume	641
DOIs	https://doi.org/10.1016/j.laa.2022.02.020
State	Published - 15 May 2022

Keywords

BFP conjecture
Bipartite graph
Degree sequence
Spectral radius

Access to Document

10.1016/j.laa.2022.02.020

Cite this

@article{b05e4f9f2f544329afe3986e177b10bc,

title = "Counterexamples of the Bhattacharya-Friedland-Peled conjecture",

abstract = "The Brualdi-Hoffman conjecture, proved by Rowlinson in 1988, characterized the graph with maximal spectral radius among all simple graphs with prescribed number of edges. In 2008, Bhattacharya, Friedland, and Peled proposed an analog, which will be called the BFP conjecture in the following, of the Brualdi-Hoffman conjecture for the bipartite graphs with fixed numbers of edges in the graph and vertices in the bipartition. The BFP conjecture was proved to be correct if the number of edges is large enough by several authors. However, in this paper we provide some counterexamples of the BFP conjecture.",

keywords = "BFP conjecture, Bipartite graph, Degree sequence, Spectral radius",

author = "Cheng, {Yen Jen} and Liu, {Chia An} and Weng, {Chih wen}",

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

year = "2022",

month = may,

day = "15",

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

language = "English",

volume = "641",

pages = "200--207",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Counterexamples of the Bhattacharya-Friedland-Peled conjecture

AU - Cheng, Yen Jen

AU - Liu, Chia An

AU - Weng, Chih wen

PY - 2022/5/15

Y1 - 2022/5/15

N2 - The Brualdi-Hoffman conjecture, proved by Rowlinson in 1988, characterized the graph with maximal spectral radius among all simple graphs with prescribed number of edges. In 2008, Bhattacharya, Friedland, and Peled proposed an analog, which will be called the BFP conjecture in the following, of the Brualdi-Hoffman conjecture for the bipartite graphs with fixed numbers of edges in the graph and vertices in the bipartition. The BFP conjecture was proved to be correct if the number of edges is large enough by several authors. However, in this paper we provide some counterexamples of the BFP conjecture.

AB - The Brualdi-Hoffman conjecture, proved by Rowlinson in 1988, characterized the graph with maximal spectral radius among all simple graphs with prescribed number of edges. In 2008, Bhattacharya, Friedland, and Peled proposed an analog, which will be called the BFP conjecture in the following, of the Brualdi-Hoffman conjecture for the bipartite graphs with fixed numbers of edges in the graph and vertices in the bipartition. The BFP conjecture was proved to be correct if the number of edges is large enough by several authors. However, in this paper we provide some counterexamples of the BFP conjecture.

KW - BFP conjecture

KW - Bipartite graph

KW - Degree sequence

KW - Spectral radius

UR - http://www.scopus.com/inward/record.url?scp=85125448091&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2022.02.020

DO - 10.1016/j.laa.2022.02.020

M3 - Article

AN - SCOPUS:85125448091

SN - 0024-3795

VL - 641

SP - 200

EP - 207

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Counterexamples of the Bhattacharya-Friedland-Peled conjecture

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this