Vertex degrees close to the average degree

DOI10.1016/J.DISC.2023.113599MaRDI QIDQ6080552zbMATH OpenFDO

Authors Johannes Pardey, Dieter Rautenbach

Publication date 4 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.07953

zbMATH Keywords

average degreedegree sequence

Mathematics Subject Classification ID

Vertex degrees (05C07)

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_{+}inleft(sqrtdn,n-1ight]$, we show the existence of a vertex in $G$ of degree between $d_{+}-left(frac(d_{+}-d)nn-d_{+}+sqrt{d}_{+}^2-dnight)$ and $d_{+}$.

Recommendations

• Mean distance and minimum degree
• Average distance, minimum degree, and size
• Using minimum degree to bound average distance
• On the Erdős-Sós conjecture and graphs with large minimum degree.
• Average degree in graph powers

Cites work

• Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 3588696 (Why is no real title available?)
• Zero-sum copies of spanning forests in zero-sum complete graphs

Cited in

(2)

• Inequalities relating degrees of adjacent vertices to the average degree
• On groupies in graphs

This page was built for publication: Vertex degrees close to the average degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080552)