BALANCED VERTEX SETS IN GRAPHS

Abstract

Let $v_{1},\ldots,v_{r}$ be a $\beta$-sequence (Definition 1.2) in an $n$-vertex graph $G$ and $v_{r+1},\ldots,v_{n}$ be the other vertices of $G$. In this paper we prove that if $v_{1},\ldots,v_{r}$ is balansed, that is \[ \frac{1}{r}(d(v_{1})+\ldots +d(v_{r})=\frac{1}{n}(d(v_{1})+\ldots +d(v_{n}),\] and if the number of edges of $G$ is big enough, then $G$ is regular.