| Given a family F = {H1, H2, ...,Hk} of graphs, we say that a graph is F -free if G contains no subgraph isomorphic to any Hi, i = 1, 2, ..., k. The graphs in the set F are known as forbidden subgraphs. In this work, we continue to classify pairs of forbidden subgraphs that imply a 3-connected graph is hamiltonian. First, we reduce the number of possible forbidden pairs by presenting families of graphs that are 3-connected and not hamiltonian. Of particular interest is the graph K1,3, also known as the claw, as we show that it must be included in any forbidden pair. Secondly, we let Ni,j,k denote the generalized net, which is the graph obtained by rooting vertex-disjoint paths of length i, j, and k at the vertices of a triangle. We show that 3-connected, {K 1,3, Ni,j,0}-free graphs are hamiltonian for i, j ≠ 0, i + j ≤ 9 and {K1,3, N3,3,3}-free graphs are hamiltonian. These results are best possible in the sense that no path of length i can be replaced by i + 1 in the above net graphs. When combined with previously known results, this completes the classification of generalized nets such that a graph being {K1,3, N i,j,k}-free implies hamiltonicity. |
