Title of article :
On a Hنggkvistʹs Conjecture with the Polynomial Method
Author/Authors :
Cلmara، نويسنده , , M. and Lladَ، نويسنده , , A. and Moragas، نويسنده , , J.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Abstract :
A conjecture of Häggkvist states that every tree with m edges decomposes every 2m–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 v 0 satisfies ρ ( T , v 0 ) ≥ ϕ 1 / 2 , where ϕ = 1 + 5 2 is the golden ratio, then T decomposes K 2 p , 2 p . We also prove that if T has at least p / 3 leaves then it decomposes K 2 p , 2 p . The results follow from an application of Alonʹs Combinatorial Nullstellensatz to obtain bigraceful labelings.
Keywords :
Graph decomposition , bigraceful labeling , polynomial method , Combinatorial Nullstellensatz , Hنggkvistיs conjecture
Journal title :
Electronic Notes in Discrete Mathematics
Journal title :
Electronic Notes in Discrete Mathematics