ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 59-66
https://doi.org/10.26493/1855-3974.1291.ee9
(Also available at http://amc-journal.eu)
On the size of maximally non-hamiltonian
digraphs*
*
Nicolas Lichiardopol
Lycee A. de Craponne, Salon, France
Carol T. Zamfirescuf
Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281-S9, 9000 Ghent, Belgium and Department of Mathematics, Babes-Bolyai University, Cluj-Napoca, Romania
A graph is called maximally non-hamiltonian if it is non-hamiltonian, yet for any two non-adjacent vertices there exists a hamiltonian path between them. In this paper, we naturally extend the concept to directed graphs and bound their size from below and above. Our results on the lower bound constitute our main contribution, while the upper bound can be obtained using a result of Lewin, but we give here a different proof. We describe digraphs attaining the upper bound, but whether our lower bound can be improved remains open.
Keywords: Maximally non-hamiltonian digraphs. Math. Subj. Class.: 05C45, 05C20
1 Introduction
Throughout this paper all graphs will be simple, finite, connected, and will not admit multiple edges or loops. In a digraph, each edge between two adjacent vertices u and v may be oriented from u to v, from v to u, or both ways. We call a digraph an oriented graph if no edge has both orientations.
*We are grateful to the referees for their helpful comments. We would also like to thank Kenta Ozeki for fruitful discussions.
t Zamfirescu is supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO). E-mail address: czamfirescu@gmail.com (Carol T. Zamfirescu)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
In memory of Nicolas Lichiardopol.
Received 14 January 2017, accepted 12 June 2018, published online 14 September 2018
Abstract
100
Ars Math. Contemp. 16 (2019) 97-109
We were led to the study of the titular subject from a related concept: homogeneous traceability, a notion introduced by Skupien. A digraph is called homogeneously traceable if every vertex is the start-vertex of a hamiltonian path. If additionally every vertex is also the end-vertex of some hamiltonian path, the digraph is called bihomogeneously traceable. A graph or digraph D is called hypohamiltonian if D is non-hamiltonian, but for any vertex v in D, the graph D - v is hamiltonian. Obviously, any digraph that is hamiltonian or hypohamiltonian is bihomogeneously traceable. But not every homogeneously traceable digraph is hamiltonian [4]. Not even bihomogeneous traceability implies hamiltonicity. At a meeting in Kalamazoo (in 1980) Skupien showed that for all n > 7 there exists a 2-diregular bihomogeneously traceable non-hamiltonian oriented digraph of order n, see [16], which appeared in 1981.
Moreover, Skupien [17] later constructed exponentially many bihomogeneously traceable non-hamiltonian oriented graphs. Independently, in another paper which also appeared in 1981, Hahn and T. Zamfirescu [12] also constructed an infinite sequence of bihomoge-neously traceable non-hamiltonian oriented graphs, and gave three special examples: the first is arc-minimal (i.e. with the smallest possible number of arcs for a given number of vertices) and order 7, the second is planar and has 8 vertices (it is proven in [12] that there are no smaller examples), and the third is both arc-minimal and planar, and has 9 vertices. Note that arc-minimality amounts in this context to 2-diregularity.
Hahn and T. Zamfirescu asked in [12] the natural question whether infinitely many planar bihomogeneously traceable non-hamiltonian oriented graphs exist, as very few were known. Infinite families of planar hypohamiltonian digraphs containing opposite arcs have been found by Fouquet and Jolivet [10]. In [20], Thomassen proved that a planar hypohamiltonian digraph with n vertices (and many edges with both orientations—in fact, all but six) exists for each n > 6. It was shown by the second author [21] that, indeed, there exist infinitely many planar bihomogeneously traceable non-hamiltonian oriented graphs. A stronger result was recently obtained by van Aardt, Burger, and Frick [1], who showed that there exist infinitely many planar hypohamiltonian oriented graphs, thereby solving a problem of Thomassen [20].
If one now asks for an even larger set of spanning paths, one may be led to the case demanding that between any two non-adjacent vertices there exists a hamiltonian path. Such graphs have been studied in the non-oriented case, see for instance [7] and [2], and are called maximally non-hamiltonian (which, in the following, will often be abbreviated to MNH). For a digraph D, we write V(D) and A(D) for its set of vertices and arcs, respectively. Mirroring the non-directed definition, a digraph D is maximally non-hamiltonian if D is non-hamiltonian, but for every x, y G V(D) with yx G A(D) there is a hamiltonian path from x to y.
A few words concerning the notation. For a set X, we denote with |X | the cardinality of X. In a graph G, for adjacent vertices x and y in G we denote by xy the edge between x and y. If G is a digraph, xy will be the arc from x to y. A digraph D is called strong if for any pair x, y G V(D) there exists a (directed) path from x to y. Denote with ¿+(D) (¿-(D)) the minimum out-degree (minimum in-degree) and with ¿0(D) the minimum semi-degree of D, which is the minimum of ¿+(D) and ¿-(D). N + (x) (N-(x)) shall be the set of out-neighbours (in-neighbours) of a vertex x. For a set of vertices S of D we denote the digraph induced by S in D as D[S]. Further definitions follow when needed.
N. Lichiardopol and C. T. Zamfirescu: On the size of maximally non-hamiltonian digraphs 61
2 Results
An important direction of research on non-directed MNH graphs has been determining the smallest size of an MNH graph of order n, which we shall denote by /(n). This study was initiated by Bondy [6], who showed that for n > 7 we have /(n) > |~3f 1. Bollobas [5] conjectured that there exist infinitely many graphs for which this lower bound is in fact attained. This was proven to be correct for all even n > 36 by Clark and Entringer [7]. In the same paper graphs of order n and size [3fl + 1 were constructed for all odd n > 55. Horak and Siran [13] also found such almost extremal graphs by using a construction of Thomassen [19] (which was originally intended to construct hypohamiltonian graphs). They also proved that for every n > 48 there exists a triangle-free MNH graph of order n.
Clark and Entringer asked in [7] whether for infinitely many n the MNH graph on n vertices of smallest size is unique or not. Combining the results from [7, 8, 9, 15], one obtains that for infinitely many n there exist two non-isomorphic MNH graphs of order n and smallest size. Still, there were infinitely many orders for which only one MNH graph of smallest size was known. This was investigated by Stacho [18]; he proved that for any n > 88 there exist three pairwise non-isomorphic MNH graphs of order n and smallest size.
In the following we extend the study of the size of MNH graphs to directed graphs. First, we characterise the non-strong MNH digraphs. A digraph is symmetric if for every arc in D the corresponding inverted arc also lies in D. For integers m > 1 and p > 1, let Dm,p denote the digraph whose vertices are the vertices of two vertex-disjoint complete symmetric digraphs Km and Kp and whose arcs are those of the digraphs Km, Kp, and additionally the arcs xy with x in Km and y in Kp. We claim:
Lemma 2.1. The non-strong MNH digraphs are the digraphs Dm,p.
Proof. Clearly, a digraph Dm p is a non-strong MNH digraph. Conversely, let D be a non-strong MNH digraph. There exists a partition V1, V2 of V(D) such that there are no arcs from V2 to V1. Let x and y be two distinct vertices of D. It is easy to see that if x, y are both in Vi or in V2 there is no hamiltonian path from x to y. Furthermore, if x is in V2 and y is in V1, there is also no hamiltonian path from x to y. Then, since D is MNH, it follows that D [V1] and D [V2] are complete symmetric digraphs and that every ordered pair xy with x e V1 and y e V2 is an arc of D. This means that D is a digraph Dm p, and so we are done.	□
The upper bound contained in the following theorem can be obtained by using a result of Lewin [14], but we choose to give here a different proof. (In fact, our proof of the upper bound is a new proof of Lewin's [14, Corollary 1].) In upcoming arguments, we require the following.
Theorem 2.2 (Ghouila-Houri [11]). A strong digraph D with ¿0(D) > |V(D)|/2 ishamil-tonian.
Theorem 2.3. For an MNH digraph D of order n > 4 we have |A(D)| < (n - 1)2 and this upper bound is attained.
Proof. There exists a vertex x e V(D) with d+(x) + d-(x) < n (for otherwise, by Theorem 2.2, D would be hamiltonian). Let us put
B = N+(x) n N-(x), A = N+(x) \ B, and C = N-(x) \ B.
100
Ars Math. Contemp. 16 (2019) 97-109
Furthermore, let a, b, and c be the respective cardinalities of A, B, and C. Clearly, for a vertex y in A or in C we have d+(y) + d_ (y) < 2n — 3. For a vertex y in B, we have d+ (y) + d_ (y) < 2n — 2, and for a vertex y not adjacent with x, we have d+ (y) + d_ (y) < 2n — 4. By addition, we get
2 x |A(D)| <
n — 1 + a(2n — 3) + b(2n — 2) + c(2n — 3) + (n — 1 — a — b — c)(2n — 4),
hence
2 x |A(D)| <
n — 1 + (n — 1)(2n — 4) + a + c + 2b =(n — 1)(2n — 3) + a + c + 2b.
But d+ (x) + d- (x) < n means that we have a + c + 2b < n — 1. It follows that
2 x |A(D)| < (n — 1)(2n — 3) + n — 1 < 2(n — 1)2,
and the upper bound is proved; it is attained since D1jn-1 and Dn-1j1 are MNH digraphs of size (n — 1)2.	□
For integers r > 1 and n with n > 2r +1 define the digraph Hn,r of order n as follows. The vertices of Hn,r are those of a complete symmetric digraph K^-r-1 and r +1 additional vertices y1,..., yr+1. Let x1,..., xr be r vertices of K^-r-1. The arcs of Hn,r are the arcs of K*-r-1, y4x where 1 < i < r + 1, x G V(K*-r-1), and x^y^ where 1 < i < r and 1 < j < r +1.
It is easy to see that a digraph Hn ,r, like its converse, is MNH, of minimum semi-degree r and of strong connectivity r.
By Theorem 2.3, the maximum size of a non-strong MNH digraph is at most (n — 1)2 and this bound is reached. It was proved in [3] that a digraph D with minimum semi-degree r and with more than
a„,r = n2 — (r + 2)n + (r + 1)2
arcs is hamiltonian. When r > (n — 1)/2, by Theorem 2.2, D is hamiltonian and therefore cannot be MNH. But when r < (n — 1)/2, the result of [3] shows that the maximum size of an MNH digraph D of order n with ¿0(D) = r is at most an,r, and since Hn,r is MNH, of minimum semi-degree r and of size an,r, this upper bound is reached.
If 1 < r < s < (n — 1)/2, then an,r > an,s, so the maximum size of an MNH digraph D of order n and of strong connectivity k(D) = r is at most an,r. As K(Hn,r) = r, the bound is sharp.
We now establish a lower bound on the size of an MNH digraph.
Lemma 2.4. For an MNH digraph D on at least four vertices, either ¿°(D) > 2 or |A(D)| > 3n — 4.
Proof. We proceed by induction on n. It is easy to verify that the assertion is true for n = 4. Now let n > 5 and suppose the assertion is true for all k < n — 1. Consider a digraph D of order n having the required property.
Let us put V (D) = {x1,...,xn}. Let there exist a vertex of D which is of out-degree at most 1. W.l.o.g., we may assume that this vertex is x1. Suppose first that d+(x1) = 0.
N. Lichiardopol and C. T. Zamfirescu: On the size of maximally non-hamiltonian digraphs 63
In this case D is a non-strong MNH digraph, and by Lemma 2.1, D is in fact D„_i i. We then have |A(D)| = (n - 1)2 > 3n - 4, and so we are done.
Suppose now that (x1) = 1. W.l.o.g., we may assume that the unique out-neighbour of x1 is x2. We claim that x2x1 G A(D). Suppose the opposite. Then there exists a hamil-tonian path P from x1 to x2. But then x1 has at least two out-neighbours, a contradiction. We also claim that all of the vertices of V(D) \ {x1, x2} are in-neighbours of x2. Suppose the opposite. Then there exists a vertex xj, i > 3, which is not an in-neighbour of x2. Thus, there exists a hamiltonian path from x2 to x^ whence, x1 has an out-neighbour in this hamiltonian path distinct from x2, a contradiction.
We claim that D' = D - x1 is MNH, i.e. that for any two vertices y, z of D' such that zy G A(D), there exists a hamiltonian path in D' from y to z. Observe first that y = x2. There exists in D a hamiltonian path P from y to z. P contains the arc x1x2, and since x1 is not the first vertex of P it admits an in-neighbour u in P. Then P' = P — x1 + ux2 (i.e. the path P from which we delete the vertex x1 and add the arc ux2) is a hamiltonian path in D' from y to z. So, the claim is proved.
By induction hypothesis, either every vertex of D' is of in-degree at least 2 in D', or |A(D')| > 3(n — 1) — 4 = 3n — 7. In the first case, since x2 is of in-degree n — 2 in D', we have |A(D') | > n — 2 + 2(n — 2), hence |A(D') | > 3n — 6. Since x1x2 and x2x1 are arcs of D but not of D', we get | A(D) | > 3n — 4, and the theorem is proved in this case.
Suppose now that |A(D')| > 3n — 7. Assume first that there are no distinct vertices xj, xj, where 3 < i, j < n, such that xjxj is not an arc of D'. Then we have |A(D')| > (n — 2)2 > 3n — 6. Thus | A(D) | > 3n — 4, and again we are done. Suppose now that there exist distinct vertices xj, xj, where 3 < i, j < n, such that xj xj G A(D'). Then there exists a hamiltonian path of D from xj to xj, and then necessarily x1 has an in-neighbour xk with 3 < k < n. It follows that | A(D) | > 3n — 7 + 3 = 3n — 4, and we are done. □
As a corollary, we can state:
Theorem 2.5. For an MNH digraph D of order n > 4 we have | A(D) | > 2n.
Proof. If | A(D) | > 3n — 4, we are done. If | A(D) | < 3n — 4, by Lemma 2.4, each vertex of D is of out-degree at least 2, and we get | A(D) | > 2n.	□
Observe that for n = 3, this lower bound inequality is untrue: consider the digraph D = ({x, y, z}, {xy, yx, xz, yz}). D is an MNH digraph of order 3 and size 4. Also note that for n = 4, the lower bound is tight due to the digraph D2 2, which is not regular.
From [6] we know that for n > 7 the size of an MNH graph of order n is at least . For every n > 19, this lower bound is reached; consult [18] and [15] for details. Thus, for n > 19, there exists an MNH graph G of order n and size . It is easy to prove that the symmetric digraph obtained by doubly orienting each edge of G is an MNH digraph of order n and size 2 x [3f a. S° the minimum size of an MNH digraph of order n > 19 is at least 2n and at most 2 x |"3f 1.
We now give a lower bound on the size of an MNH non-strong digraph:
Theorem 2.6. Let D be an MNH non-strong digraph of order n > 2. Then
3
|A(D)|> - n2 — n.
100
Ars Math. Contemp. 16 (2019) 97-109
Proof. We know that D is of the form Dan,(1-a)n, where 0 < a < 1 and an is an integer. Then we have
|A(D)| = an(an — 1) + (1 — a)n((1 — a)n — 1) + an(1 — a)n = n2(a2 — a +1) — n > 4n2 — n,
since a2 — a + 1 > 4.
□
If the strong connectivity is 1, we have the following result.
Theorem 2.7. Let D be an MNH digraph of order n > 4 and of strong connectivity 1. Then
|A(D)| > min < 3n — 4, 5
2 n
1
Proof. If S+ (D) < 1 or S-(D) < 1, by Lemma 2.4, we have | A(D)| > 3n — 4, and the result is proved.
Suppose now that S+ (D) > 2 and S- (D) > 2, i.e. each vertex of D is of out-degree at least 2 and of in-degree at least 2. There is a vertex x such that the digraph D — x is not strong, so there exists a partition of V(D) \ {x} into two non-empty sets A and B such that there are no arcs from B to A. W.l.o.g., we suppose that |B| < |A|, so |A| > 2. We claim that all the vertices of B are out-neighbours of x. Let us suppose this not to be the case. Then there exists a vertex y of B such that xy G A(D). Since D is MNH, there exists a hamiltonian path P from y to x. Necessarily, P contains an arc uv with u G B and v G A, which is impossible. Similarly, all the vertices of A are in-neighbours of x. Since x has at least one out-neighbour in A and at least one in-neighbour in B, we get d+(x) + d- (x) > n + 1.
Suppose now that x has exactly one out-neighbour y in A. It is easy to see that A \ {y}, B U {x} is a partition of V(D) \ {y} into non-empty sets such that there are no arcs from B U {x} to A \ {y}. So, D — y is not strong, and from the preceding arguments, we have d+(y) + d-(y) > n + 1. Since d+(z) + d-(z) > 4 for z distinct from x and y, by addition we get 2 x |A(D)| > 2(n + 1) + 4(n — 2), hence 2 x |A(D)| > 6n — 6, and | A(D) | > 3n — 3 > 3n — 4, and the result is proved.
Suppose now that x has at least two out-neighbours in A. We then get d+ (x) + d- (x) > n + 2, and for z = x we have d+(z) + d-(z) > 4. By addition this yields 2 x |A(D)| > n + 2 + 4(n — 1), hence |A(D)| > [§ n] — 1, as stated.
With above conclusions in mind, an MNH digraph D with
□
|A(D)| < min < 3n — 4
5 2 n
1,
3	2
4	n
is necessarily of strong connectivity at least 2, and thus, of semi-degree at least 2. Now it is easy to see that for n > 5, if the lower bound 2n is attained by an MNH digraph D of order n, then necessarily D is a 2-diregular digraph of order n and of strong connectivity 2. We were not able to show the existence of such digraphs, but an advance in this direction is perhaps the following:
n
Theorem 2.8. Let D be a 2-diregular MNH digraph of order n. Then D is hypohamilto-nian.
N. Lichiardopol and C. T. Zamfirescu: On the size of maximally non-hamiltonian digraphs 65
Proof. We know that D is non-hamiltonian. Suppose for the sake of a contradiction that there exists a vertex z such that D — z is non-hamiltonian. Let x be an in-neighbour of z, and let y be the other out-neighbour of x. We claim that zy G A(D). Suppose the opposite. Then there exists a hamiltonian path from y to z, and it is easy to see that the in-neighbour of z in P is x. But then P — z + xy is a hamiltonian cycle of D — z, a contradiction.
Assume that y is an in-neighbour of z. Then y and z are of in-degree 2 in the induced sub-digraph D[{x, y, z}]. Since D is 2-strong and n > 5, this is not possible. Therefore y is not an in-neighbour of z. Suppose that x is an out-neighbour of z. Then x and z are of out-degree 2 in the induced sub-digraph D[{x, y, z}]. Since D is 2-strong and n > 5, this is not possible.
So x is not an out-neighbour of z. Then z has an in-neighbour u distinct from x, y, and z. The vertex y is not an out-neighbour of u (for otherwise y would be of in-degree at least 3, which is impossible), and x is not an out-neighbour of u (for otherwise, with a previous argument, zx would be an arc of D, which is false). Thus u has an out-neighbour v distinct from x, y, and z. Then, by previous arguments, zv is an arc of D, and v is not an in-neighbour of z. The last statement implies that there exists a hamiltonian path P' from z to v. The second vertex of P' is necessarily y, and then it is easy to see that x has an out-neighbour w distinct from y and z. Since x is of out-degree 2, this is impossible. Thus D — z cannot be non-hamiltonian, and so the theorem is proved.	□
The above discussions concerning the size of MNH digraphs led us to the following question.
Problem. Does every non-hamiltonian oriented graph of order at least 3 contain an arc xy for which there is no hamiltonian path from x to y?
Lastly, we would like to point out the connection between maximally non-hamiltonian graphs and so-called platypus, which are non-hamiltonian graphs in which every vertex-deleted subgraph is traceable. They contain the family of all hypohamiltonian and hy-potraceable graphs. The second author showed [22] that a maximally non-hamiltonian graph G is a platypus if and only if A(G) < |V(G)| — 1, where A(G) denotes the maximum degree of G. Directed platypus have not yet been investigated, but the above results may provide a good starting point.
References
[1]	S. A. van Aardt, A. P. Burger and M. Frick, An Infinite Family of Planar Hypohamiltonian Oriented Graphs, Graphs Combin. 29 (2013), 729-733, doi:10.1007/s00373-012-1165-z.
[2]	A. Ainouche and N. Christofides, Conditions for the existence of hamiltonian circuits in graphs based on vertex degrees, J. London Math. Soc. 32 (1985), 385-391, doi:10.1112/jlms/s2-32.3. 385.
[3]	D. Amar, I. Fournier and A. Germa, Some conditions for digraphs to be Hamiltonian, in: M. Rosenfeld and J. Zaks (eds.), Convexity and Graph Theory, North-Holland, Amsterdam, volume 20 of Annals of Discrete Mathematics, 1984 pp. 37-41, doi:10.1016/s0304-0208(08) 72804-4, proceedings of the conference held in Jerusalem, March 16 - 20, 1981.
[4]	J.-C. Bermond, J. M. S. Simoes-Pereira and C. M. Zamfirescu, On nonhamiltonian homogeneously traceable digraphs, Math. Japonica 24 (1979), 423-426.
[5]	B. Bollobas, Extremal Graph Theory, volume 11 of London Mathematical Society Monographs, Academic Press, London, 1978.
100
Ars Math. Contemp. 16 (2019) 97-109
[6]	J. A. Bondy, Variations on the Hamiltonian theme, Canad. Math. Bull. 15 (1972), 57-62, doi: 10.4153/cmb-1972-012-3.
[7]	L. Clark and R. Entringer, Smallest maximally nonhamiltonian graphs, Period. Math. Hungar. 14 (1983), 57-68, doi:10.1007/bf02023582.
[8]	L. H. Clark, R. P. Crane, R. C. Entringer and H. D. Shapiro, On smallest maximally nonhamiltonian graphs, in: F. Hoffman, R. C. Mullin, R. G. Stanton and K. B. Reid (eds.), Proceedings of the Seventeenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, Winnipeg, Manitoba, volume 53 of Congressus Numerantium, 1986 pp. 215-220, held at Florida Atlantic University, Boca Raton, Florida, February 10- 14, 1986.
[9]	L. H. Clark, R. C. Entringer and H. D. Shapiro, Smallest maximally nonhamiltonian graphs II, Graphs Combin. 8 (1992), 225-231, doi:10.1007/bf02349959.
[10]	J.-L. Fouquet and J.-L. Jolivet, Hypohamiltonian oriented graphs, Cahiers Centre Etudes Rech. Oper. 20 (1978), 171-181.
[11]	A. Ghouila-Houri, Une condition suffisante d'existence d'un circuit hamiltonien, C. R. Acad. Sci. Paris 251 (1960), 495-497.
[12]	S. Hahn and T. Zamfirescu, Bihomogeneously traceable oriented graphs, Rend. Sem. Mat. Univ. Politec. Torino 39 (1981), 137-145.
[13]	P. Horak and J. Siran, On a construction of Thomassen, Graphs Combin. 2 (1986), 347-350, doi:10.1007/bf01788108.
[14]	M. Lewin, On maximal circuits in directed graphs, J. Comb. Theory Ser. B 18 (1975), 175-179, doi:10.1016/0095-8956(75)90045-3.
[15]	X. Lin, W. Jiang, C. Zhang and Y. Yang, On Smallest Maximally Non-Hamiltonian Graphs, Ars Combin. 45 (1997), 263-270.
[16]	Z. Skupien, On homogeneously traceable non-Hamiltonian digraphs and oriented graphs, in: G. Chartrand, Y. Alavi, D. L. Goldsmith, L. Lesniak-Foster and D. R. Lick (eds.), The Theory and Applications of Graphs, John Wiley & Sons, New York, 1981 pp. 517-527, proceedings of the Fourth International Conference held at Western Michigan University, Kalamazoo, Michigan, May 6-9, 1980.
[17]	Z. Skupien, Exponential constructions of some non-Hamiltonian minima, in: J. Nesetril and M. Fiedler (eds.), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, North-Holland, Amsterdam, volume 51 of Annals of Discrete Mathematics, 1992 pp. 321-328, doi:10.1016/s0167-5060(08)70649-6, proceedings of the symposium held in Prachatice, 1990.
[18]	L. Stacho, Non-Isomorphic Smallest Maximally Non-Hamiltonian Graphs, Ars Combin. 48 (1998), 307-317.
[19]	C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math. 9 (1974), 91-96, doi:10.1016/0012-365x(74)90074-0.
[20]	C. Thomassen, Hypohamiltonian graphs and digraphs, in: Y. Alavi and D. R. Lick (eds.), Theory and Applications of Graphs, Springer-Verlag, Berlin, volume 642 of Lecture Notes in Mathematics, 1978 pp. 557-571, proceedings of the International Conference held at Western Michigan University, Kalamazoo, Michigan, May 11 - 15, 1976.
[21]	C. T. Zamfirescu, An Infinite Family of Planar Non-Hamiltonian Bihomogeneously Traceable Oriented Graphs, Graphs Combin. 26 (2010), 141-146, doi:10.1007/s00373-010-0900-6.
[22]	C. T. Zamfirescu, On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable, J. Graph Theory 86 (2017), 223-243, doi:10.1002/jgt.22122.