An Update on Supereulerian Graphs
An Update on Supereulerian Graphs
复制标题
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
H. Lai;Yehong Shao
中科院分区：
文献类型：
--
作者：
H. Lai;Yehong Shao
一个图是超欧拉图，如果它有一个生成欧拉子图。受中国邮政员问题的启发，Boesch，Suffel和Tindell([2])在1997年提出了超欧拉问题，寻求具有欧拉子图生成的图的特征，并指出这个问题将是非常困难的。Pulley Blank([71])在1979年晚些时候证明了判定一个图是否超欧拉，即使是在平面图中，也是NP完全的。从那时起，人们对这一话题进行了大量的研究。Catlin([7])在1992年首次提出了关于超欧拉图的研究。本文旨在对Catlin的综述文章进行更新，并将重点介绍近20年来超欧拉图的研究进展及相关问题。关键词：欧拉图、超欧拉图、可折叠图、Catlin约简法、折线图、无爪图
A graph is supereulerian if it has a spanning Eulerian subgraph. Motivated by the Chinese Postman Problem, Boesch, Suffel, and Tindell ([2]) in 1997 proposed the supereulerian problem, which seeks a characterization of graphs that have spanning Eulerian subgraphs, and they indicated that this problem would be very difficult. Pulleyblank ([71]) later in 1979 proved that determining whether a graph is supereulerian, even within planar graphs, is NP-complete. Since then, there have been lots of researches on this topic. Catlin ([7]) in 1992 presented the first survey on supereulerian graphs. This paper is intended as an update of Catlin’s survey article and will focus on the developments in the study of supereulerian graphs and the related problems over the past 20 years. Key–Words: Eulerian graphs, Supereulerian graphs, Collapsible graphs, Catlin’s reduction method, Line graphs, Claw-free graphs