Vol. 10, No. 5, 2017

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
The Hamiltonian problem and $t$-path traceable graphs

Kashif Bari and Michael E. O’Sullivan

Vol. 10 (2017), No. 5, 801–812
Abstract

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.

Keywords
maximal non-hamiltonian, hamiltonian, graph theory, t-path traceable
Primary: 05C45