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.

05C45 Eulerian and Hamiltonian graphs
PDF BibTeX Cite