Name
Abstract | ||
|---|---|---|
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 integers {1,..., q} such that all p vertex sums are pairwise distinct, where the vertex sum on a vertex is the sum of labels of all edges incident to such vertex.
A graph is called anti-magic if it has an anti-magic labeling. Hartsfield and Ringel [3] conjectured that all connected graphs
except K
2 are anti-magic. Recently, N. Alon et al [1] showed that this conjecture is true for p-vertex graphs with minimum degree Ω(log p). They also proved that complete partite graphs except K
2 and graphs with maximum degree at least p–2 are anti-magic. In this article, some new classes of anti-magic graphs are constructed through Cartesian products. Among
others, the toroidal grids C
m
× C
n
(the Cartesian product of two cycles), and the higher dimensional toroidal grids Cm1 ×Cm2 ×...... ×CmtC_{m_1} \times C_{m_2} \times ...... \times C_{m_t}, are shown to be anti-magic. Moreover, the more general result is also proved to be true: H × C
n
(hence C
n
× H) is anti-magic, where H is an anti-magic k-regular graph, where k>1.
|
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11533719_68 | Computing and Combinatorics |
Keywords | Field | DocType |
vertex sum,anti-magic k-regular graph,cartesian product,edges incident,anti-magic graph,connected graph,p vertex,toroidal grid,log p,complete partite graph,p vertex sum,regular graph,maximum degree | Complete graph,Discrete mathematics,Combinatorics,Multigraph,Vertex (geometry),Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Regular graph,Degree (graph theory),Mathematics | Conference |
Volume | ISSN | ISBN |
3595 | 0302-9743 | 3-540-28061-8 |
Citations | PageRank | References |
12 | 1.74 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tao-Ming Wang | 1 | 59 | 12.79 |