# Pairs of Forbidden Subgraphs for Pancyclicity (2012)

Originators: Ron Gould    (presented by Tim Morris - REGS 2012)

Definitions: Let $\mathcal{F}$ be a set of graphs. A graph $G$ is $\mathcal{F}-$free if $G$ has no graph in $\mathcal F$ as an induced subgraph. A graph $G$ is pancyclic if $G$ contains cycles of all lengths from $3$ to $|V(G)|$. A graph is Hamiltonian if it contains a spanning cycle.

Background: Matthews and Sumner [MS] conjectured that every $4$-connected claw-free graph is hamiltonian. Brandt, Favaron, and Ryjáček [BFR] showed that for every $k\ge 2$ there is a $k$-connected claw-free graph that is not pancyclic. Thus it makes sense to investigate what pairs $\{X,Y\}$ of graphs have the property that every a 4-connected $\{X,Y\}$-free graph is pancyclic.

Problem: Determine the maximal graphs $H$ such that every $4$-connected $({\rm claw},H)$-free graph is pancyclic. Call such a graph $H$ sufficient.

Comments: The generalized net $N(i,j,k)$ is the unicyclic graph consisting of a triangle plus pendant paths of lengths $i$, $j$, and $k$ grown from the three vertices of the triangle. It is known that $N(i,j,0)$ is sufficient when $i+j=6$ [FGGMP]. Also $P_9$ is sufficient [FMW].

Let $L_5$ denote the line graph of the graph obtained from $K_5$ by subdividing each edge once. Because $L_5$ and the line graph of the Petersen graph are not pancyclic, every such graph $H$ must be an induced subgraph of both of these graphs. Thus, the list of candidates for $H$ is small. They include a few generalized nets, lassos, and a 6-cycle with the endpoints of every other edge associated with a single vertex one of which is has a pendant off of it. They include only the following graphs and induced subgraphs of them.

Question: Are there other 4-connected claw-free non-pancyclic graphs to rule out any of the remaining possibilities (by not containing them)?

Comments: One way to attempt to find graphs to rule out any of these possibilities is to take a 4-connected graph, subdivide (some of) the edges once and then take the line graph of the resulting graph. This gives you a 4-connected claw-free graph.

References:
[MS] M.M. Matthews, D.P. Sumner, Hamiltonian results in $K_{1,3}$-free graphs, J. Graph Theory 8 (1984) 139-146.
[BFR] S. Brandt, O. Favaron, Z. Ryjáček, Closure and stable Hamiltonian properties in claw-free graphs, J. Graph Theory 34 (2000) 30-41.
[FMW] Ferrara, M.; Morris, T. and Wenger, P. Pancyclicity of 4-Connected, Claw-free, $P_{10}$-free Graphs. In Journal of Graph Theory, (2012).
[FGGMP] Ferrara, M.; Gehrke, S.; Gould R. and Powell, J. Pancyclicity of 4-connected $\{$claw, generalized net$\}$-free graphs, (submitted)