Spanning paths in graphs

Abstract

The Conjecture, Graffiti.pc 190, of the computer program Graffiti.pc, instructed by DeLavi˜na, state that every simple connected graph G with minimum degree δ and leaf number L(G) such that δ ≥ 1 2 (L(G) + 1), is traceable. Here, we prove a sufficient condition for a graph to be traceable based on minimum degree and leaf number, by settling completely, the Conjecture Graffiti. pc 190. We construct infinite graphs to show that our results are best in a sense. All graphs considered are simple. That is, they neither have loops nor multiple edges.