← Back to Search
Infinite Families Of 2-hypohamiltonian/2-hypotraceable Oriented Graphs
Published 2014 · Mathematics, Computer Science
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
A digraph D of order n is r-hypohamiltonian (respectively r-hypotraceable) for some positive integer r < n − 1 if D is nonhamiltonian (nontraceable) and the deletion of any r of its vertices leaves a hamiltonian (traceable) digraph. A 1-hypohamiltonian (1-traceable) digraph is simply called hypohamiltonian (hypotraceable). Although hypohamiltonian and hypotraceable digraphs are well-known and well-studied concepts, we have found no mention of r-hypohamiltonian or r-hypotraceable digraphs in the literature for any r > 1. In this paper we present infinitely many 2-hypohamiltonian oriented graphs and use these to construct infinitely many 2-hypotraceable oriented graphs. We also discuss an interesting connection between the existence of r-hypotraceable oriented graphs and the Path Partition Conjecture for oriented graphs.