错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Every graph is homeomorphic to an antimagic bipartite graph

  • Joaquín Tey,
  • Ilan A. Goldfeder,
  • Nahid Y. Javier-Nol

摘要

An antimagic labeling of a graph G is a bijection from E(G) to \(\{1,2,\dots ,\vert E(G)\vert \}\) { 1 , 2 , , | E ( G ) | } such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if the resulting graph of deleting its isolated vertices admits an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every connected graph other than \(K_2\) K 2 is antimagic, a conjecture that remains widely open; particularly for graphs with many vertices of degree two, with a few exceptions. Two graphs are homeomorphic if both can be obtained from the same graph by subdivisions of edges. In this note, we prove that every simple graph (connected or not) is homeomorphic to an antimagic bipartite graph. Consequently, we also show that every simple graph is homeomorphic to a graph that admits an antimagic orientation.