PreprintarXiv licencearXiv
Maximum spread of vertex degrees in a simple graph
Abstract
We consider the following problem: let n>k --- positive integers, G --- a graph on n vertices (undirected, without loops or multiple edges). Let hk(G) denote the number of unordered pairs of vertices of the graph G whose degrees differ by less than k. We seek to determine the smallest possible value f(n,k) of hk(G). The interest in this question is motivated by the fact that the bipartite analogue of the problem allowed S. Cichomski and F. Petrov \cite{CP} to prove the Burdzy--Pitman conjecture on the spread of independent identically distributed random variables.
Related
- Approximating Distributions on Vertex Degrees in Random Hypergraphs via Stein's Method
- Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
- Short Paper No. 1: Relation between integer sequence A319433 and the maximum degrees of finite linear Jaco graphs
- Maximum Likelihood Degrees via One-Edge Chordal Completion
- Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
BibTeX
@misc{onishchenko2026maximum,
title = {{Maximum spread of vertex degrees in a simple graph}},
author = {Sergey Onishchenko},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.27537},
eprint = {2608.27537},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27537},
}
RIS
TY - UNPB
TI - Maximum spread of vertex degrees in a simple graph
AU - Sergey Onishchenko
PY - 2026
DA - 2026/08/27
PB - arXiv
DO - 10.48550/arxiv.2608.27537
UR - https://arxiv.org/abs/2608.27537
AB - We consider the following problem: let n>k --- positive integers, G --- a graph on n vertices (undirected, without loops or multiple edges). Let h_k(G) denote the number of unordered pairs of vertices of the graph G whose degrees differ by less than k. We seek to determine the smallest possible value f(n,k) of h_k(G). The interest in this question is motivated by the fact that the bipartite analogue of the problem allowed S. Cichomski and F. Petrov \cite{CP} to prove the Burdzy--Pitman conjecture on the spread of independent identically distributed random variables.
ER -