×
Lichiardopol, Nicolas; Zamfirescu, Carol T.

On the size of maximally non-Hamiltonian digraphs. (English) Zbl 1416.05166

Ars Math. Contemp. 16, No. 1, 59-66 (2019).
Summary: 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 M. Lewin [J. Comb. Theory, Ser. B 18, 175–179 (1975; Zbl 0297.05119)], but we give here a different proof. We describe digraphs attaining the upper bound, but whether our lower bound can be improved remains open.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
05C12 Distance in graphs
05C35 Extremal problems in graph theory

Keywords:

maximally non-Hamiltonian digraphs

Citations:

Zbl 0297.05119
Cite Review PDF
Full Text: DOI

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. · Zbl 1268.05095
[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. · Zbl 0598.05045
[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. · Zbl 0561.05029
[4] J.-C. Bermond, J. M. S. Sim˜oes-Pereira and C. M. Zamfirescu, On nonhamiltonian homogeneously traceable digraphs, Math. Japonica 24 (1979), 423-426. · Zbl 0422.05030
[5] B. Bollob´as, Extremal Graph Theory, volume 11 of London Mathematical Society Monographs, Academic Press, London, 1978. · Zbl 0419.05031
[6] J. A. Bondy, Variations on the Hamiltonian theme, Canad. Math. Bull. 15 (1972), 57-62, doi: 10.4153/cmb-1972-012-3. · Zbl 0238.05115
[7] L. Clark and R. Entringer, Smallest maximally nonhamiltonian graphs, Period. Math. Hungar. 14 (1983), 57-68, doi:10.1007/bf02023582. · Zbl 0489.05038
[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. · Zbl 0641.05035
[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. · Zbl 0758.05066
[10] J.-L. Fouquet and J.-L. Jolivet, Hypohamiltonian oriented graphs, Cahiers Centre ´Etudes Rech. Op´er.20 (1978), 171-181. · Zbl 0381.05039
[11] A. Ghouila-Houri, Une condition suffisante d’existence d’un circuit hamiltonien, C. R. Acad. Sci. Paris251 (1960), 495-497. · Zbl 0091.37503
[12] S. Hahn and T. Zamfirescu, Bihomogeneously traceable oriented graphs, Rend. Sem. Mat. Univ. Politec. Torino39 (1981), 137-145. · Zbl 0518.05036
[13] P. Hor´ak and J. ˇSir´aˇn, On a construction of Thomassen, Graphs Combin. 2 (1986), 347-350, doi:10.1007/bf01788108. · Zbl 0612.05041
[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. · Zbl 0297.05119
[15] X. Lin, W. Jiang, C. Zhang and Y. Yang, On Smallest Maximally Non-Hamiltonian Graphs, Ars Combin.45 (1997), 263-270. · Zbl 0933.05071
[16] Z. Skupie´n, 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. · Zbl 0472.05026
[17] Z. Skupie´n, Exponential constructions of some non-Hamiltonian minima, in: J. Neˇsetˇril 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. · Zbl 0763.05068
[18] L. Stacho, Non-Isomorphic Smallest Maximally Non-Hamiltonian Graphs, Ars Combin. 48 (1998), 307-317. · Zbl 0962.05034
[19] C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math. 9 (1974), 91-96, doi:10.1016/0012-365x(74)90074-0. · Zbl 0278.05110
[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. · Zbl 0371.05015
[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. · Zbl 1231.05163
[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. · Zbl 1370.05115
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.