zbMATH — the first resource for mathematics

Exponential constructions of some nonhamiltonian minima. (English) Zbl 0763.05068
Combinatorics, graphs and complexity, Proc. 4th Czech. Symp., Prachatice/Czech. 1990, Ann. Discrete Math. 51, 321-328 (1992).
Summary: [For the entire collection see Zbl 0748.00023.]
Exponentially many $$n$$-vertex minimum nonhamiltonian (A) homogeneously traceable graphs and (B) bihomogeneously traceable oriented graphs are constructed. An analog of Sylvester’s result on numerical semigroups is used.

MSC:
 05C45 Eulerian and Hamiltonian graphs