Vertex degrees close to the average degree

2023/01/19 by Pardey, Johannes, Rautenbach, Dieter
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2301.07953

Abstract

Let G be a finite, simple, and undirected graph of order n and average degree d. Up to terms of smaller order, we characterize the minimal intervals I containing d that are guaranteed to contain some vertex degree. In particular, for d₊∈ (√(dn),n-1], we show the existence of a vertex in G of degree between d₊-(((d₊-d)n)/(n-d₊+√(d₊²-dn))) and d₊.

Related

• Graph Partitions Under Average Degree Constraint
• Infinite graphs that do not contain cycles of length four
• Small subgraphs with large average degree
• Sparse vertex cutsets and the maximum degree
• Average Degree in Graph Powers