Local and global average degree in bipartite graphs
arXiv:2607.14038
summary
The paper determines the asymptotic value of the maximum ratio between the smallest local average degree and the overall average degree in n‑vertex bipartite graphs without isolated vertices, proving it equals ¼√n + 3/8 + o(1).
Abstract
Let denote the maximum, over all -vertex bipartite graphs without isolated vertices, of the ratio of the minimum local average degree to the global average degree. We prove that . This answers a problem posed by Tuza.
9 pages
Topics & keywords
#bipartite graphs#average degree#extremal graph theory#asymptotic analysislocal average degreeglobal average degreeF_bip(n)asymptotic formulaTuza problem