An application of the combinatorial Nullstellensatz to a graph labelling problem |
| |
Authors: | Dan Hefetz Annina Saluz Huong T. T. Tran |
| |
Affiliation: | 1. Institute of Theoretical Computer Science, ETH Zurich, CH‐8092, Switzerland;2. Department of Mathematics, ETH Zurich, CH‐8092, Switzerland;3. Institute of Mathematics, 18 Hoang Quoc Viet, 10307 Hanoi, Vietnam |
| |
Abstract: | An antimagic labelling of a graph G with m edges and n vertices is a bijection from the set of edges of G to the set of integers {1,…,m}, such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labelling. In N. Hartsfield and G. Ringle, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, Ringel has conjectured that every simple connected graph, other than K2, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=pk vertices, where p is an odd prime and k is a positive integer that admits a Cp‐factor, then it is antimagic. The case p=3 was proved in D. Hefetz, J Graph Theory 50 (2005), 263–272. Our main tool is the combinatorial Nullstellensatz [N. Alon, Combin Probab Comput 8(1–2) (1999), 7–29]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 70–82, 2010. |
| |
Keywords: | Combinatorial Nullstellensatz graph labelling |
|
|