Search Results

You are looking at 1 - 3 of 3 items for

  • Author or Editor: R. Entringer x
Clear All Modify Search

A graphG ismaximally nonhamiltonian iffG is not hamiltonian butG + e is hamiltonian for each edgee inG c, i.e., any two non-adjacent vertices ofG are ends of a hamiltonian path. Bollobás posed the problem of finding the least number of edges,f(n), possible in a maximally nonhamiltonian graph of ordern. Results of Bondy show thatf(n)3/2 n forn ≤ 7. We exhibit graphs of even ordern ≥ 36 for which the bound is attained. These graphs are the “snarks”,J k, of Isaacs and mild variations of them. For oddn ≥ 55 we construct graphs from the graphsJ k showing that in this case,f(n) = 3n + 1/2 or 3n + 3/2 and leave the determination of which is correct as an open problem. Finally we note that the graphsJ k, k ≤ 7 are hypohamiltonian cubics with girth 6.

Restricted access
Authors: G. J. Simmons and R. C. Entringer

For small values of n it is easily seen that the components of a bigraph on 2n points are themselves bigraphs of their point set.Simmons had asked whether this was always the case and had shown that if a bigraph on 2n points existed which had a component that was not in itself a bigraph then 2n≧16. In this paper we answer his question affirmatively by using a result ofLovász. We also show that any two components of a bigraph intersect.

Restricted access
Authors: R. C. Entringer, P. Erdős and C. C. Harner
Restricted access