Constructing Hypohamiltonian Snarks with Cyclic Connectivity 5 and 6 A graph is hypohamiltonian if it is not hamiltonian but every vertexdeleted subgraph is. In this paper we study hypohamiltonian snarks xe2x80x93 cubic hypohamiltonian graphs with chromatic index 4. We describe a method, based on superposition of snarks, which produces new hypohamiltonian snarks from old ones. By choosing suitable ingredients we can achieve that the resulting graphs are cyclically 5connected or 6connected.  Previously, only three sporadic hypohamiltonian snarks with cyclic connectivity 5 had been found, while the flower snarks of Isaacs were the only known family of cyclically 6connected hypohamiltonian snarks.  Our method produces hypohamiltonian snarks with cyclic connectivity 5 and 6 for all but finitely many even orders.

Subgraph isomorphism on graph classes that exclude a substructure We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus on the minor relation since other wellknown relations lead to either trivial or equivalent problems. When the forbidden minor is connected, we present a near dichotomy of the complexity of Subgraph Isomorphism with respect to the forbidden minor, where the only unsettled case is the path of five vertices. We then also consider the general case of possibly disconnected forbidden minors. We show in particular that: the problem is fixedparameter tractable parameterized by the size of the forbidden minor H when H is a linear forest such that at most one component has four vertices and all other components have three or less vertices; and it is NPcomplete if H contains four or more components with at least five vertices each. As a byproduct, we show that Subgraph Isomorphism is fixedparameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that Subgraph Isomorphism is fixedparameter tractable parameterized by neighborhood diversity.