Planar Hypohamiltonian Graphs on 40 Vertices
A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer‐aided generation of certain families of planar graphs with girth 4 and a fixed number of 4‐faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.
Small hypohamiltonian graphs
A graph G is said to be hypohamiltonian if G is not hamiltonian but for each v ∈ V (G) the vertex deleted subgraph G − v is hamiltonian. In this paper we show that there is no hypohamiltonian graph on 17 vertices and thereby complete the answer to the question, “for which values of n do there exist hypohamiltonian graphs on n vertices?”. In addition we present an exhaustive list of hypohamiltonian graphs on fewer than 18 vertices and extend previously obtained results for cubic hypohamiltonian graphs.
Best approximation and moduli of smoothness: Computation and equivalence theorems
In this paper we investigate the trigonometric series with the @b-general monotone coefficients. First, we study the uniform convergence criterion. The estimates of best approximations and moduli of smoothness of the series in uniform metrics are obtained in terms of coefficients. These results imply several important relations between moduli of smoothness of different orders (in particular, Marchaud-type inequality) and best approximations.