首页 | 本学科首页   官方微博 | 高级检索  
     


Graphs of Large Linear Size Are Antimagic
Authors:Tom Eccles
Affiliation:DEPARTMENT OF PURE MATHEMATICS AND MATHEMATICAL STATISTICS, UNIVERSITY OF CAMBRIDGE, UNITED KINGDOM
Abstract:Given a graph urn:x-wiley:03649024:media:jgt21872:jgt21872-math-0001 and a colouring urn:x-wiley:03649024:media:jgt21872:jgt21872-math-0002, the induced colour of a vertex v is the sum of the colours at the edges incident with v. If all the induced colours of vertices of G are distinct, the colouring is called antimagic. If G has a bijective antimagic colouring urn:x-wiley:03649024:media:jgt21872:jgt21872-math-0003, the graph G is called antimagic. A conjecture of Hartsfield and Ringel states that all connected graphs other than K2 are antimagic. Alon, Kaplan, Lev, Roddity and Yuster proved this conjecture for graphs with minimum degree at least urn:x-wiley:03649024:media:jgt21872:jgt21872-math-0004 for some constant c; we improve on this result, proving the conjecture for graphs with average degree at least some constant d0.
Keywords:antimagic  labelling
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号