Online citations, reference lists, and bibliographies.
← Back to Search

Infinite Families Of 2-hypohamiltonian/2-hypotraceable Oriented Graphs

S. V. Aardt, A. Burger, M. Frick, B. Llano, R. Zuazua
Published 2014 · Mathematics, Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Share
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.
Get Citationsy
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.
This paper references
campanological problem in group theory
R. A. Rankin (1948)
10.1017/S0305004100039451
A campanological problem in group theory. II
R. A. Rankin (1966)
10.21236/ad0705364
Graph theory
F. Harary (1969)
10.1016/0095-8956(72)90048-2
A two-connected planar graph without concurrent longest paths
T. Zamfirescu (1972)
10.1016/0097-3165(74)90025-9
Vertices Missed by Longest Paths or Circuits
B. Grünbaum (1974)
10.7146/MATH.SCAND.A-11630
On longest paths and circuits in graphs.
T. Zamfirescu (1976)
10.1007/BFB0070410
Hypohamiltonian graphs and digraphs
Carsten Thomassen (1978)
10.1002/jgt.3190040406
Hypotraceable digraphs
M. Grötschel (1980)
10.1002/jgt.3190070409
When the cartesian product of two directed cycles is hypo-Hamiltonian
Laurence E. Penn (1983)
Constructions of hypotraceable digraphs
M. Grötschel (1984)
10.1002/jgt.3190110105
When the cartesian product of two directed cycles is hyperhamiltonian
J. Gallian (1987)
10.1007/BF01158712
Locally Hamiltonian graphs
D. Katona (1989)
Mathematical Notes 45(1) (1989) 25-29 (translated from Mat
D. Katona (1989)
Hypohamiltonian/hypotraceable digraphs abound
Z. Skupień (1997)
10.1002/(SICI)1097-0118(199904)30:4%3C319::AID-JGT6%3E3.0.CO;2-1
On non-Hamiltonian circulant digraphs of outdegree three
S. Locke (1999)
Digraphs - theory, algorithms and applications
J. Bang-Jensen (2002)
10.37236/874
A Traceability Conjecture for Oriented Graphs
M. Frick (2008)
Progress on the Traceability Conjecture for Oriented Graphs
M. Frick (2008)
Digraphs - Theory, Algorithms and Applications, Second Edition
J. Bang-Jensen (2009)
10.1016/j.disc.2009.12.022
Traceability of k-traceable oriented graphs
S. V. Aardt (2010)
10.1016/j.disc.2011.03.009
The order of hypotraceable oriented graphs
S. V. Aardt (2011)
10.37236/2499
Computational Results on the Traceability of Oriented Graphs of Small Order
B. Ap (2013)
10.1007/s00373-012-1165-z
An Infinite Family of Planar Hypohamiltonian Oriented Graphs
S. V. Aardt (2013)
10.37236/2499
Computational Results on the Traceability of Oriented Graphs of Small Order
Alewyn Burger (2013)
10.37236/2498
An Iterative Approach to the Traceability Conjecture for Oriented Graphs
S. V. Aardt (2013)



This paper is referenced by
Semantic Scholar Logo Some data provided by SemanticScholar