Independent sets and partitions of graphs

I.V.Protasov; K.D.Protasova

Let $\Gamma(V,E)$ be a connected graph with the set of vertices $V$ and the set of edges $E$, $d$ be the path metric on $V$, $B(v,r)=\{x\in V\colon d(v,x)\leq r\}$ be the ball of radius $r$ with the center $v\in V$. A subset $S\subseteq V$ is of finite index if there exists $r$ such that $\bigcup _{v\in S} B(v,r)=V$, and the minimal $r$ satisfying this condition is called the index of $S$.\ The paper consists of two parts. In the first part we use the independent subsets in $\Gamma(V,E)$ to partition $V$ in the subsets of controlled finite indices. In the second part we propose an approach to the balanced partitions of infinite graphs in the subsets of finite index.

1. F. Lazebnik, A.J. Woldar, General properties of some families of graphs defined by system of equations, J. Graph Theory, 38 (2001), no. 2, 65-68.

2. I.V. Protasov, Quasiray decomposition of infinite graphs, Math. Stud., 17 (2002), 274-276.

3. I.V. Protasov, T. Banakh, Ball structures and colorings of groups and graphs, Mat. Stud. Monogr. Ser., vol. 11, VNTL Publisher, Lviv, 2003.

4. I.V. Protasov, K.D. Protasova, Automorphisms of kaleidoscopical graphs, Algebra Discrete Math., 2007, no.2, 125-129.

5. I.V. Protasov, K.D. Protasova, Kaleidoscopical graphs and Hamming codes, in Voronoi's Impact on Modern Science, Institute Mathematics, NAS Ukraine, Kyiv 2008, book 4, vol. 1, 240-245.

6. K.D. Protasova, Kaleidoscopical graphs, Mat. Stud., 18 (2002), 3-9.

7. K.D. Protasova, Balanced partition of graphs, Matem. Zamet., 79 (2006), 127-132.

8. P.Turan, Eine Extremalaufgabe aus der Graphentheorie, Math. Fiz. Lapok, 48 (1941), 436-452.

9. V.A.Ustimenko, Coordinatization of trees and their quotiens, in Voronoi's Impact on Modern Science, Institute Mathematics, NAS Ukraine, Kyiv 1998, book 1, vol. 2, 125-152.

10. A.J. Wolder, Rainbow graphs, Codes and designs (Columbus, OH, 2000), 313-322, Ohio State Univ. Math. Res. Inst. Publ., 10, de Grueter, Berlin, 2002.

	Independent sets and partitions of graphs
Author	I.V.Protasov, K.D.Protasova protasov@unicyb.kiev.ua, islab@unicyb.kiev.ua Department of Cybernetics, Kyiv University, Volodimirska str. 64, Kyiv 01033, UKRAINE
Abstract	Let $\Gamma(V,E)$ be a connected graph with the set of vertices $V$ and the set of edges $E$, $d$ be the path metric on $V$, $B(v,r)=\{x\in V\colon d(v,x)\leq r\}$ be the ball of radius $r$ with the center $v\in V$. A subset $S\subseteq V$ is of finite index if there exists $r$ such that $\bigcup _{v\in S} B(v,r)=V$, and the minimal $r$ satisfying this condition is called the index of $S$.\ The paper consists of two parts. In the first part we use the independent subsets in $\Gamma(V,E)$ to partition $V$ in the subsets of controlled finite indices. In the second part we propose an approach to the balanced partitions of infinite graphs in the subsets of finite index.
Keywords	partition of graph, finite index, balanced partition, infinite graph
DOI	doi:10.30970/ms.33.1.3-10
Reference	1. F. Lazebnik, A.J. Woldar, General properties of some families of graphs defined by system of equations, J. Graph Theory, 38 (2001), no. 2, 65-68. 2. I.V. Protasov, Quasiray decomposition of infinite graphs, Math. Stud., 17 (2002), 274-276. 3. I.V. Protasov, T. Banakh, Ball structures and colorings of groups and graphs, Mat. Stud. Monogr. Ser., vol. 11, VNTL Publisher, Lviv, 2003. 4. I.V. Protasov, K.D. Protasova, Automorphisms of kaleidoscopical graphs, Algebra Discrete Math., 2007, no.2, 125-129. 5. I.V. Protasov, K.D. Protasova, Kaleidoscopical graphs and Hamming codes, in Voronoi's Impact on Modern Science, Institute Mathematics, NAS Ukraine, Kyiv 2008, book 4, vol. 1, 240-245. 6. K.D. Protasova, Kaleidoscopical graphs, Mat. Stud., 18 (2002), 3-9. 7. K.D. Protasova, Balanced partition of graphs, Matem. Zamet., 79 (2006), 127-132. 8. P.Turan, Eine Extremalaufgabe aus der Graphentheorie, Math. Fiz. Lapok, 48 (1941), 436-452. 9. V.A.Ustimenko, Coordinatization of trees and their quotiens, in Voronoi's Impact on Modern Science, Institute Mathematics, NAS Ukraine, Kyiv 1998, book 1, vol. 2, 125-152. 10. A.J. Wolder, Rainbow graphs, Codes and designs (Columbus, OH, 2000), 313-322, Ohio State Univ. Math. Res. Inst. Publ., 10, de Grueter, Berlin, 2002.
Pages	3-10
Volume	33
Issue	1
Year	2010
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html