Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
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: Mar 1 2018

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)
Bookmark and Share
  Reviewer Selected
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy