zbMATH — the first resource for mathematics

Antimagic labelling of vertex weighted graphs. (English) Zbl 1244.05192
Summary: Suppose \(G\) is a graph, \(k\) is a non-negative integer. We say \(G\) is \(k\)-antimagic if there is an injection \(f: E\to \{1, 2, \dots , |E| + k\}\) such that for any two distinct vertices \(u\) and \(v\), \(\sum_{e\in E(v)}f(e)\neq\sum_{e\in E(u)}f(e)\). We say \(G\) is weighted-\(k\)-antimagic if for any vertex weight function \(w: V\to \mathbb N\), there is an injection \(f: E\to \{1, 2, \dots , |E| + k\}\) such that for any two distinct vertices \(u\) and \(v\), \(\sum_{e\in E(v)}f(e)+w(v)\neq\sum_{e\in E(u)}f(e)+w(u)\).
A well-known conjecture asserts that every connected graph \(G\neq K_{2}\) is 0-antimagic. On the other hand, there are connected graphs \(G\neq K_{2}\) which are not weighted-1-antimagic. It is unknown whether every connected graph \(G\neq K_{2}\) is weighted-2-antimagic.
In this paper, we prove that if \(G\) has a universal vertex, then \(G\) is weighted-2-antimagic. If \(G\) has a prime number of vertices and has a Hamiltonian path, then \(G\) is weighted-1-antimagic. We also prove that every connected graph \(G\neq K_{2}\) on \(n\) vertices is weighted-\(\lfloor 3n/2\rfloor \)-antimagic.

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C22 Signed and weighted graphs
Full Text: DOI
[1] Alon, Combinatorial Nullstellensatz, Probab Comput 8 pp 7– (1999) · Zbl 0920.05026 · doi:10.1017/S0963548398003411
[2] Alon, Dense graphs are antimagic, J Graph Theory 47 pp 297– (2004) · Zbl 1055.05132 · doi:10.1002/jgt.20027
[3] Cheng, Lattice grids and prisms are antimagic, Theoret Comput Sci 374 pp 66– (2007) · Zbl 1162.05040 · doi:10.1016/j.tcs.2006.12.003
[4] Y. Cheng Cartesian products of regular graphs are antimagic
[5] Hartsfield, Pearls in Graph Theory pp 108– (1990) · Zbl 0703.05001
[6] Hefetz, Anti-magic graphs via the combinatorial nullstellensatz, J Graph Theory 50 pp 263– (2005) · Zbl 1076.05068 · doi:10.1002/jgt.20112
[7] Hefetz, An application of the Combinatorial Nullstellensatz to a graph labelling problem, J Graph Theory (2009) · Zbl 1209.05214 · doi:10.1002/jgt.20466
[8] Kaplan, On zero-sum partitions and antimagic trees, Discrete Math 309 pp 2010– (2009) · Zbl 1229.05031 · doi:10.1016/j.disc.2008.04.012
[9] Y. Liang T. Wong X. Zhu Antimagic labeling of trees 2010
[10] Scheim, The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete Math 8 pp 377– (1974) · Zbl 0281.05103 · doi:10.1016/0012-365X(74)90157-5
[11] Wang, Toroidal grids are antimagic pp 671– (2005)
[12] Wang, On antimagic labelling for graph products, Discrete Math 308 pp 3624– (2008) · Zbl 1155.05055 · doi:10.1016/j.disc.2007.07.027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.