On cycle lengths in claw-free graphs with complete closure (Q960969)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On cycle lengths in claw-free graphs with complete closure
scientific article

    Statements

    On cycle lengths in claw-free graphs with complete closure (English)
    0 references
    0 references
    0 references
    0 references
    29 March 2010
    0 references
    For a graph \(G\), let \(N(v)\) be the set of vertices adjacent to \(v\), and \(G[N(x)]\) be the subgraph induced by \(N(x)\). A vertex \(x \in V(G)\) is \textit{eligible} if \(G[N(x)]\) is a connected noncomplete graph. The \textit{completion} of \(G\) at a vertex \(x\) is the graph obtained from \(G\) by adding the edges in \(\{ uv \not \in E(G): u, v \in N(x) \}\). The \textit{closure} \(cl(G)\) of a claw-free graph \(G\), introduced by \textit{Z. Ryjáček} [J. Comb. Theory, Ser. B 70, 217--224 (1997; Zbl 0872.05032)], is obtained from \(G\) by recursively performing the completion at the eligible vertices until no eligible vertex remains. For each pair \((k, \lambda)\) satisfying \(\lambda \geq 33\) when \(2 \leq k \leq 4\), and \(\lambda \geq 52\) if \(k = 5\), the authors construct an infinite family of claw-free graphs of connectivity \(k\) with complete closure and containing no cycle of length \(\lambda\). These graphs are counterexamples to a conjecture posed by the \textit{Z. Ryjáček}, \textit{A. Saito}, and \textit{R. Schelp} [Discrete Math. 236, No.1-3, 325--338 (2001; Zbl 0995.05080)]. On the other hand, they restate another conjecture by \textit{Z. Ryjáček, A. Saito} and \textit{R. Schelp} [loc. cit.] that if \(c\) is a fixed constant, then for large \(n\), every claw-free graph with complete closure on \(n\) vertices contains cycles of length \(i\) for all \(i\), \(n - c \leq i \leq n\). They also conjecture that every \(6\)-connected claw-free graph with complete closure on \(n\) vertices contains cycles of length \(i\) for all \(i\), \(3 \leq i \leq n\).
    0 references
    0 references
    closure
    0 references
    claw-free graph
    0 references
    cycle length
    0 references
    pancyclicity
    0 references

    Identifiers