WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 12, 2013
An Update on Supereulerian Graphs
Authors: , ,
Abstract: 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.
Search Articles
Keywords: Eulerian graphs, Supereulerian graphs, Collapsible graphs, Catlin’s reduction method, graphs, Claw-free graphs