Zero-sum partition theorems for graphs
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.
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1994-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171294000992 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832563616844349440 |
|---|---|
| author | Y. Caro I. Krasikov Y. Roditty |
| author_facet | Y. Caro I. Krasikov Y. Roditty |
| author_sort | Y. Caro |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-12595769eaf840a88183e7452bc104bb |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 1994-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-12595769eaf840a88183e7452bc104bb2025-02-03T01:12:58ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04251994-01-0117469770210.1155/S0161171294000992Zero-sum partition theorems for graphsY. Caro0I. Krasikov1Y. Roditty2Department of Mathematics, Haifa University, Oranim, IsraelSchool of Mathematics, Tel-Aviv University, Ramat Aviv, IsraelSchool of Mathematics, Tel-Aviv University, Ramat Aviv, IsraelLet 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.http://dx.doi.org/10.1155/S0161171294000992zero-sumpartitionclique-number. |
| spellingShingle | Y. Caro I. Krasikov Y. Roditty Zero-sum partition theorems for graphs International Journal of Mathematics and Mathematical Sciences zero-sum partition clique-number. |
| title | Zero-sum partition theorems for graphs |
| title_full | Zero-sum partition theorems for graphs |
| title_fullStr | Zero-sum partition theorems for graphs |
| title_full_unstemmed | Zero-sum partition theorems for graphs |
| title_short | Zero-sum partition theorems for graphs |
| title_sort | zero sum partition theorems for graphs |
| topic | zero-sum partition clique-number. |
| url | http://dx.doi.org/10.1155/S0161171294000992 |
| work_keys_str_mv | AT ycaro zerosumpartitiontheoremsforgraphs AT ikrasikov zerosumpartitiontheoremsforgraphs AT yroditty zerosumpartitiontheoremsforgraphs |