PreprintarXiv licencearXiv
Local versus global average degree in bipartite graphs
Abstract
Let Fbip(n) denote the maximum, over all n-vertex bipartite graphs without isolated vertices, of the ratio of the minimum local average degree to the global average degree. We prove that Fbip(n)=1/4√n+3/8+o(1). This answers a problem posed by Tuza. The lower bound is obtained from a new family of bipartite constructions, while the upper bound is proved by a new algebraic approach, different from the combinatorial methods used previously. The key ingredient is a spectral argument based on a normalized biadjacency matrix.
Related
- Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
- P-stable degree sequence regions for bipartite and directed graphs
- Proper Conflict-Free Choosability for Graphs with Bounded Average Degree
- The diameter of recoloring graphs under a maximum average degree bound
- Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
BibTeX
@misc{hou2026local,
title = {{Local versus global average degree in bipartite graphs}},
author = {Jianfeng Hou and Hongbin Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.14038},
eprint = {2607.14038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.14038},
}
RIS
TY - UNPB
TI - Local versus global average degree in bipartite graphs
AU - Jianfeng Hou
AU - Hongbin Zhao
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2607.14038
UR - https://arxiv.org/abs/2607.14038
AB - Let F_bip(n) denote the maximum, over all n-vertex bipartite graphs without isolated vertices, of the ratio of the minimum local average degree to the global average degree. We prove that F_bip(n)=1/4√n+3/8+o(1). This answers a problem posed by Tuza. The lower bound is obtained from a new family of bipartite constructions, while the upper bound is proved by a new algebraic approach, different from the combinatorial methods used previously. The key ingredient is a spectral argument based on a normalized biadjacency matrix.
ER -