On Antimagic Labeling of Odd Regular Graphs

详细信息    查看全文

• 作者：Tao-Ming Wang (18)
  Guang-Hui Zhang (18)
  
• 关键词：antimagic labeling ; regular graph ; perfect matching ; 2 ; factor ; generalized Petersen graph ; Cayley graph ; circulant graph
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7643
• 期：1
• 页码：169-181
• 全文大小：408KB
• 参考文献：1. Alon, N., Kaplan, G., Lev, A., Roditty, Y., Yuster, R.: Dense graphs are antimagic. Journal of Graph Theory?47(4), 297-09 (2004) CrossRef
  2. Miller, M., Ba?a, M.: Antimagic valuations of generalized Petersen graphs. Australasian Journal of Combinatorics?22, 135-39 (2000)
  3. Ba?a, M., Jendrol, S., Miller, M., Ryan, J.: Antimagic Labelings of Generalized Petersen Graphs That Are Plane. Ars Combinatoria (2004)
  4. Barrus, M.D.: Antimagic labeling and canonical decomposition of graphs. Information Processing Letters?110(7), 261-63 (2010) CrossRef
  5. Cheng, Y.: A new class of antimagic Cartesian product graphs. Discrete Mathematics?308(24), 6441-448 (2008) CrossRef
  6. Cheng, Y.: Lattice grids and prisms are antimagic. Theoretical Computer Science?374(1V3), 66-3 (2007) CrossRef
  7. Cranston, D.: Regular bipartite graphs are antimagic. Journal of Graph Theory?60(3), 173-82 (2009) CrossRef
  8. Gallian, J.A.: A dynamic survey of graph labeling. The Electronic Journal of Combinatorics?DS6, 1-9 (2001)
  9. Hartsfield, N., Ringel, G.: Pearls in Graph Theory, pp. 108-09. Academic Press, Inc., Boston (1990) (Revised version 1994)
  10. Hefetz, D.: Anti-magic graphs via the combinatorial nullstellensatz. Journal of Graph Theory?50(4), 263-72 (2005) CrossRef
  11. Huang, P.Y., Wong, T.L., Zhu, X.: Weighted-1-antimagic graphs of prime power order. To appear in Discrete Mathematics (2011)
  12. Lee, M., Lin, C., Tsai, W.: On Antimagic Labeling For Power of Cycles. Ars Combinatoria?98, 161-65 (2011)
  13. Petersen, J.: Die Theorie der regularen graphs. Acta Mathematica?(15), 193-20 (1891)
  14. Stewart, B.M.: Magic graphs. Canadian Journal of Mathematics?18, 1031-059 (1966) CrossRef
  15. Wang, T.-M.: Toroidal Grids Are Anti-magic. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.?3595, pp. 671-79. Springer, Heidelberg (2005) CrossRef
  16. Wang, T.M., Hsiao, C.C.: On Antimagic Labeling for Graph Products. Discrete Mathematics?308, 3624-633 (2008) CrossRef
  17. Wong, T.L., Zhu, X.: Antimagic labelling of vertex weighted graphs. To appear in Journal of Graph Theory (2011)
  18. Zhang, Y., Sun, X.: The antimagicness of the Cartesian product of graphs. Theoretical Computer Science?410, 727-35 (2009) CrossRef
  
• 作者单位：Tao-Ming Wang (18)
  Guang-Hui Zhang (18)
  
  18. Department of Applied Mathematics, Tunghai University, Taichung, 40704, Taiwan, R.O.C
  
• ISSN：1611-3349

文摘

An antimagic labeling of a finite simple undirected graph with q edges is a bijection from the set of edges to the set of integers {1, 2,??- q} such that the vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of labels of all edges incident to such vertex. A graph is called antimagic if it admits an antimagic labeling. It was conjectured by N. Hartsfield and G. Ringel in 1990 that all connected graphs besides K 2 are antimagic. Another weaker version of the conjecture is every regular graph is antimagic except K 2. Both conjectures remain unsettled so far. In this article, certain classes of regular graphs of odd degree with particular type of perfect matchings are shown to be antimagic. As a byproduct, all generalized Petersen graphs and some subclass of Cayley graphs of ?sub class="a-plus-plus"> n are antimagic.