DIKUL - logo
E-viri
Celotno besedilo
Recenzirano
  • An application of the combi...
    Hefetz, Dan; Saluz, Annina; Tran, Huong T. T.

    Journal of graph theory, September 2010, Letnik: 65, Številka: 1
    Journal Article

    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.