Antimagic labelling of vertex weighted graphs

✍ Scribed by Tsai-Lien Wong; Xuding Zhu

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 151 KB
• Volume: 70
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20624

✦ Synopsis

Abstract

Suppose G is a graph, k is a non‐negative integer. We say G is k‐antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted‐k‐antimagic if for any vertex weight function w: V→ℕ, there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . A well‐known conjecture asserts that every connected graph G≠K~2~ is 0‐antimagic. On the other hand, there are connected graphs G≠K~2~ which are not weighted‐1‐antimagic. It is unknown whether every connected graph G≠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≠K~2~ on n vertices is weighted‐ ⌊3__n__/2⌋‐antimagic. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory