International Journal of Mathematics and Mathematical Sciences
Volume 17 (1994), Issue 4, Pages 697-702
doi:10.1155/S0161171294000992

Zero-sum partition theorems for graphs

Y. Caro,1 I. Krasikov,2,3 and Y. Roditty2,3

1Department of Mathematics, Haifa University, Oranim, Israel
2School of Mathematics, Tel-Aviv University, Ramat Aviv, Israel
3Department of Mathematics, Beit-Berl College, Kfar-Saba, Israel

Received 13 November 1992; Revised 2 February 1993

Copyright © 1994 Y. Caro et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Let q=pn be a power of an odd prime p. We show that the vertices of every graph G can be partitioned into t(q) classes V(G)=⋃t=1t(q)Vi such that the number of edges in any induced subgraph 〈Vi〉 is divisible by q, where t(q)≤32(q−1)−(2(q−1)−1)124+98, and if q=2n, then t(q)=2q−1.

In particular, it is shown that t(3)=3 and 4≤t(5)≤5.