On cycle lengths in claw-free graphs with complete closure
type: Item
instance of: scholarly article
title: On cycle lengths in claw-free graphs with complete closure
zbMATH Open document ID: 1208.05062
author: Zdeněk Ryjáček
author: Zdzisław Skupień
author: Petr Vrána
published in: Discrete Mathematics
publication date: 2010-03-29T00:00:00Z
review text: 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\).
reviewed by: Ya-Chen Chen
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C63
zbMATH DE Number: 5687592
zbMATH Keywords: closure
zbMATH Keywords: claw-free graph
zbMATH Keywords: cycle length
zbMATH Keywords: pancyclicity
MaRDI profile type: Publication
full work available at URL: j.disc.2009.03.053
OpenAlex ID: W2090981096
cites work: Constructions for cubic graphs with large girth
cites work: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
cites work: The number of matchings in random regular graphs and bipartite graphs
cites work: Q5422499
cites work: Closure and stable Hamiltonian properties in claw-free graphs
cites work: Cubic Ramanujan graphs
cites work: A trivalent graph of girth 17
cites work: A canonical representation of trivalent hamiltonian graphs
cites work: Q3318798
cites work: Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
cites work: Q3204495
cites work: Almost all cubic graphs are Hamiltonian
cites work: Almost all regular graphs are hamiltonian
cites work: On a closure concept in claw-free graphs
cites work: Claw-free graphs with complete closure
cites work: The asymptotic connectivity of labelled regular graphs
cites work: The asymptotic distribution of short cycles in random regular graphs
cites work: Q4263664
DOI: 10.1016/J.DISC.2009.03.053
Recommended article: Strengthening the closure concept in claw-free graphs
Recommended article: Claw-free graphs with complete closure
Recommended article: Circumferences and minimum degrees in 3-connected claw-free graphs
Recommended article: Q4693654
Recommended article: Circumferences and Minimum Degrees in 3-Connected Claw-Free Graphs
Recommended article: Q4030544
Recommended article: Degree conditions on induced claws
Recommended article: Q4367136
Recommended article: Q5463358
Recommended article: Q4329146
description: scientific article; zbMATH DE number 5687592