Eulerian Subgraphs in Graphs with Short Cycles

Paul A. Catlin1, Hong-Jian Lai2
1Department of Mathematics, Wayne State University, Detroit MI 48202
2Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ont. CANADA N2L 3G1i

Abstract

P. Paulraja recently showed that if every edge of a graph \(G\) lies in a cycle of length at most \(5\) and if \(G\) has no induced \(K_{i,s}\) as a subgraph, then \(G\) has a spanning closed trail. We use a weaker hypothesis to obtain a stronger conclusion. We also give a related sufficient condition for the existence of a closed trail in \(G\) that contains at least one end of each edge of \(G\).