BALANCED VERTEX SETS IN GRAPHS

Nikolay Khadzhiivanov; Nedyalko Nenov

BALANCED VERTEX SETS IN GRAPHS

Authors

Nikolay Khadzhiivanov
Nedyalko Nenov

Keywords:

balanced sequence, generalized r-partite graph, generalized Turan's graph, saturated sequence

Abstract

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

Downloads

Published

2005-12-12

How to Cite

Khadzhiivanov, N., & Nenov, N. (2005). BALANCED VERTEX SETS IN GRAPHS. Ann. Sofia Univ. Fac. Math. And Inf., 97, 81–95. Retrieved from https://annual.uni-sofia.bg/index.php/fmi/article/view/145