An infinite family of planar non-Hamiltonian bihomogeneously traceable oriented graphs. (English) Zbl 1231.05163

Zamfirescu, Carol T.

Graphs Comb. 26, No. 1, 141-146 (2010).

Summary: We answer an open question on planar non-hamiltonian bihomogeneously traceable digraphs without opposite arcs by constructing an infinite family of such graphs.

MSC:

05C45	Eulerian and Hamiltonian graphs
05C20	Directed graphs (digraphs), tournaments
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

planar; bihomogeneously traceable; digraph

References:

[1]	Bermond J.-C., Simões-Pereira J.M.S., Zamfirescu C.M.: On hamiltonian homogeneously traceable digraphs. Math. Jpn. 24, 423–426 (1979) · Zbl 0422.05030
[2]	Fouquet J.-L., Jolivet J.-L.: Hypohamiltonian oriented graphs. Cahiers Centre Études Rech. Opér 20, 171–181 (1978) · Zbl 0381.05039
[3]	Grötschel M., Wakabayashi Y.: Hypohamiltonian digraphs. J. Methods Oper. Res. 36, 99–119 (1980) · Zbl 0436.05038
[4]	Hahn S., Zamfirescu T.: Bihomogeneously traceable oriented graphs. Rend. Sem. Mat. Univ. Politec. Torino 39(2), 137–145 (1981) · Zbl 0518.05036
[5]	Skupień, Z.: On homogeneously traceable nonhamiltonian digraphs and oriented graphs. In: Proc. Fourth Int. Conf. on the Theory and Appl. of Graphs, Kalamazoo (MI) 1980, pp. 517–527. Wiley, New York (1981)
[6]	Skupień, Z.: Exponential constructions of some nonhamiltonian minima. In: Proc. Fourth CS Symposium on Combinatorics, Graphs and Complexity, Prachatice 1990, Ann. Discrete Math., vol. 51, pp. 321–328 (1992) · Zbl 0763.05068
[7]	Thomassen, C.: Hypohamiltonian graphs and digraphs. In: Proc. Int. Conf. on the Theory and Appl. of Graphs, Kalamazoo (MI) 1976, Lect. Notes Math., vol. 642, pp. 557–571. Springer, Berlin (1978) · Zbl 0371.05015