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
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
closure
0 references
claw-free graph
0 references
cycle length
0 references
pancyclicity
0 references
0 references
0 references