On the Erdős-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings
1992; Elsevier BV; Volume: 110; Issue: 1-3 Linguagem: Inglês
10.1016/0012-365x(92)90695-c
ISSN1872-681X
Autores Tópico(s)Advanced Graph Theory Research
ResumoA link between Ramsey numbers for stars and matchings and the Erdős-Ginzburg-Ziv theorem is established. Known results are generalized. Among other results we prove the following two theorems. Theorem 5. Let m be an even integer. If c : e (K2m−1)→{0, 1,…, m−1} is a mapping of the edges of the complete graph on 2m−1 vertices into {0, 1,…, m−1}, then there exists a star K1,m in K2m−1 with edges e1, e2,…, em such that c(e1)+c(e2)+⋯+c(em)≡0 (mod m). Theorem 8. Let m be an integer. If c : e(Kr(r+1)m−1)→{0, 1,…, m−1} is a mapping of all the r-subsets of an (r+1)m−1 element set S into {0, 1,…, m−1}, then there are m pairwise disjoint r-subsets Z1, Z2,…, Zm of S such that c(Z1)+c(Z2)+⋯+c(Zm)≡0 (mod m).
Referência(s)