Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648757 | Discrete Mathematics | 2008 | 10 Pages |
An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q}{1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K2K2 are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p -vertex graphs with minimum degree Ω(logp)Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.