- Title
- Approximate results for rainbow labelings
- Creator
- Lladó, Anna; Miller, Mirka
- Relation
- Periodica Mathematica Hungarica Vol. 74, Issue 1, p. 11-21
- Publisher Link
- http://dx.doi.org/10.1007/s10998-016-0151-2
- Publisher
- Akademiai Kiado
- Resource Type
- journal article
- Date
- 2017
- Description
- A simple graph G = (V, E) is said to be antimagic if there exists a bijection f : E → [1,|E|] such that the sum of the values of f on edges incident to a vertex takes different values on distinct vertices. The graph G is distance antimagic if there exists a bijection f : V → [1,|V|], such that ∀x,y ∈ V, [formula could not be replicated]. Using the polynomial method of Alon we prove that there are antimagic injections of any graph G with n vertices and m edges in the interval [1, 2n+m −4] and, for trees with k inner vertices, in the interval [1, m+k]. In particular, a tree all of whose inner vertices are adjacent to a leaf is antimagic. This gives a partial positive answer to a conjecture by Hartsfield and Ringel. We also show that there are distance antimagic injections of a graph G with order n and maximum degree Δ in the interval [1, n+t(n−t)], where t = min{Δ,⌊n/2⌋}, and, for trees with k leaves, in the interval [1,3n−4k]. In particular, all trees with n = 2k vertices and no pairs of leaves sharing their neighbour are distance antimagic, a partial solution to a conjecture of Arumugam.
- Subject
- graph labeling; polynomial method
- Identifier
- http://hdl.handle.net/1959.13/1392118
- Identifier
- uon:33348
- Identifier
- ISSN:0031-5303
- Language
- eng
- Reviewed
- Hits: 694
- Visitors: 810
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|