The Hamiltonian problem and t-path traceable graphs
Kashif Bari, Michael E. O’Sullivan · Involve a Journal of Mathematics · 2017
The problem of characterizing maximal non-Hamiltonian graphs may be naturally extended to characterizing graphs that are maximal with respect to nontraceability and beyond that to t-path traceability.We show how t-path traceability behaves with respect to disjoint union of graphs and the join with a complete graph.Our main result is a decomposition theorem that reduces the problem of characterizing maximal t-path traceable graphs to characterizing those that have no universal vertex.We generalize a construction of maximal nontraceable graphs by Zelinka to t-path traceable graphs.