Computing Reviews

Antimagic labeling of regular graphs
Chang F., Liang Y., Pan Z., Zhu X. Journal of Graph Theory82(4):339-349,2016.Type:Article
Date Reviewed: 03/01/18

This paper consists of five interesting lemmas and a theorem on certain antimagic regular graphs. The well-written paper makes for absolutely delightful reading. It contains many newly introduced, well-explained, well-illustrated notations and notions.

An antimagic labeling of a graph G=(V,E) is a bijective function f:E→ {1,2, . . . ,|E|} such that the sum of labels of edges incident on distinct vertices are distinct. An antimagic graph is a graph with an antimagic labeling.

A Y-link of a bipartite graph G=(XY, E) is a 2-path with both end points in Y and Y-link of G is a family of vertex disjoint Y-links. Let v* be a vertex of G and let Li be the set of vertices in G, which are at a distance i from v*. If σ denotes a mapping from V(G) - v* to the edge set of G, with respect to which each vertex uLi is assigned an edge σ(u) of G [Li-1, Li] incident to u, then the authors infer that σ(u) cannot be a linking edge for any uLi. If G σ[Li-1, Li] is the subgraph of G [Li-1, Li], obtained by deleting all the edges {σ(u):uLi} and Gσ[Li-1, Li] is the subgraph of Gσ [Li-1, Li] obtained by deleting all the linking edges, a bad component of Gσ [Li-1, Li] is a 2-regular component H of it such that all vertices of HLi are covered by linking edges. An Li-link uvu’ in Fi is free, if one of u and u’ does not belong to any bad component of Gσ[Li-1, Li]. Invoking these notions, it is proven that Gσ[Li-1, Li] has a bad component, and implies Fi contains at least k free Li-links. If ni, ai, bi and ci respectively denote the cardinalities of Li, E(G[Li]), E(Gσ[Li-1, Li]), and E(Gσ[Li-1, Li]), then the authors proved that f(ujvj) ≤ di+ai+bi+ci - k, for any link edge ujvj and uj is a vertex in a bad component and the sum of labels of edges in E(u)-σ(u) is less than or equal to (2k+1)(di+ai)+(k+1)bi+ci+k. Hence, the key result of the paper, which states that all (2k + 2)-regular graphs are antimagic for any integer k ≥ 1, follows immediately.

Reviewer:  Sudev Naduvath Review #: CR145893 (1805-0241)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy