On a conjecture of Graham and Häggkvist with the polynomial method |
| |
Authors: | M. C mara, A. Llad ,J. Moragas |
| |
Affiliation: | aDepartament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Jordi Girona 1-3, E-08034 Barcelona, Spain |
| |
Abstract: | A conjecture of Graham and Häggkvist states that every tree with m edges decomposes every 2m-regular graph and every bipartite m-regular graph. Let T be a tree with a prime number p of edges. We show that if the growth ratio of T at some vertex v0 satisfies ρ(T,v0)≥1/2, where is the golden ratio, then T decomposes K2p,2p. We also prove that if T has at least p/3 leaves then it decomposes K2p,2p. This improves previous results by Häggkvist and by Lladó and López. The results follow from an application of Alon’s Combinatorial Nullstellensatz to obtain bigraceful labelings. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|