The Hamiltonian problem and t-path traceable graphs

Bari, Kashif; O’Sullivan, Michael

doi:10.2140/involve.2017.10.801

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

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

DOI: 10.2140/involve.2017.10.801

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

Mathematical Subject Classification 2010

Primary: 05C45

Milestones

Received: 7 February 2016

Revised: 23 June 2016

Accepted: 24 July 2016

Published: 14 May 2017

Communicated by Ronald Gould

Authors

Kashif Bari
Department of Mathematics and Statistics San Diego State University San Diego, CA 92182 United States

Michael E. O’Sullivan
Department of Mathematics and Statistics San Diego State University San Diego, CA 92182 United States

Vol. 10, No. 5, 2017