An application of the combinatorial Nullstellensatz to a graph labelling problem

✍ Scribed by Dan Hefetz; Annina Saluz; Huong T. T. Tran

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 130 KB
• Volume: 65
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20466

✦ Synopsis

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 K~2~, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=p^k^ vertices, where p is an odd prime and k is a positive integer that admits a C~p~‐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.