Smallest k-edge-connected claw-free graphs without special spanning trails
Abstract
Harris and Mossinghoff [7] and Bullock, Frick and Singleton [3] determined the smallest 2-connected non-traceable claw-free graphs G1, G 2 . In this paper, we consider the analogues for 2-edge-connected graphs and trails, determine the smallest 2-edge-connected claw-free graphs without a spanning trail and the smallest 2-edge-connected non-traceable claw-free graphs. It is interesting that the graphs of the first conclusion are also G1,G2, and the second can be deduced by the line graph closure of Ryjáček and by the following result: if G has no cut-vertex of degree two and of order at most 10, then either G has a dominating trail, or G belongs to one of four special graphs. We also determine the smallest K-edge-connected non-supereulerian claw-free graph for k = 2,3.
