Skip to main content
SpringerLink
Log in

An Infinite Family of Planar Hypohamiltonian Oriented Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Carsten Thomassen asked in 1976 whether there exists a planar hypohamiltonian oriented graph. We answer his question by presenting an infinite family of planar hypohamiltonian oriented graphs, the smallest of which has order 9. A computer search showed that 9 is the smallest possible order of a hypohamiltonian oriented graph.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Hahn S., Zamfirescu T.: Bihomogeneously traceable oriented graphs. Rend. Sem. Mat Univ. Politec. Torino 39(2), 137–145 (1981)

    MathSciNet  MATH  Google Scholar 

  2. Skupień, Z.: On homogeneously traceable nonhamiltonian digraphs and oriented graphs. In: Chartrand, G., Alavi, Y., Goldsmith, D.L., Lesniak-Foster, L., Lick, D.R. (eds.) The Theory and Applications of Graphs (Proc. Fourth Int. Conf. on T.A.G., held in Kalamazoo, MI., 1980), pp. 517–527. Wiley (1981)

  3. Thomassen, C.: Hypohamiltonian graphs and digraphs. In: Proceedings of the International Conference on the Theory and Applications of Graphs, Kalamazoo, 1976, pp. 557–571. Springer Verlag, Berlin (1978)

  4. van Aardt S.A., Frick M., Katrenič P., Nielsen M.H.: The order of hypotraceable oriented graphs. Discret. Math. 311, 1273–1280 (2011)

    Article  MATH  Google Scholar 

  5. Zamfirescu C.T.: An infinite family of planar non-hamiltonian bihomogeneusly traceable oriented graphs. Graphs Comb. 26, 141–146 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, University of South Africa (UNISA), PO BOX 392, Pretoria, 0003, South Africa

    Susan A. van Aardt & Marietjie Frick

  2. Department of Logistics, University of Stellenbosch, Private Bag X1, Matieland, Stellenbosch, 7602, South Africa

    Alewyn P. Burger

Authors
  1. Susan A. van Aardt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alewyn P. Burger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marietjie Frick
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alewyn P. Burger.

Additional information

This material is based upon work supported by the National Research Foundation of S.A. under Grant number 71308.

Rights and permissions

Reprints and permissions

About this article

Cite this article

van Aardt, S.A., Burger, A.P. & Frick, M. An Infinite Family of Planar Hypohamiltonian Oriented Graphs. Graphs and Combinatorics 29, 729–733 (2013). https://doi.org/10.1007/s00373-012-1165-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1165-z

Keywords

Mathematics Subject Classification

Search

Navigation