Premium
An application of the combinatorial Nullstellensatz to a graph labelling problem
Author(s) -
Hefetz Dan,
Saluz Annina,
Tran Huong T. T.
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20466
Subject(s) - combinatorics , mathematics , bijection , conjecture , edge graceful labeling , vertex (graph theory) , graph labeling , graph , simple graph , discrete mathematics , arithmetic progression , line graph , graph power
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.