
A graph \(G= (V,E)\) on \(n\) vertices is pancyclic if it has cycles of all lengths \(3,4,\dots, n\) and subpancyclic if it has cycles of all lengths \(3,4,\dots, c(G)\), where \(c(G)\) denotes the length of a longest cycle in \(G\). A graph is claw-free if it does not contain an induced copy \(K_{1,3}\). The authors prove that if the minimum degree \(\delta(G)\) of a claw-free graph \(G\) on \(n\) vertices is at least \(\sqrt{3n+1}-1\) then \(G\) is subpancyclic. They also show that this degree bound is best possible. This immediately implies that if a Hamiltonian claw-free graph \(G\) has minimum degree at least \(\sqrt{3n+1}-1\) then \(G\) is pancyclic. In contrast, Flandrin et al. have shown that in order to guarantee that a claw-free graph (on at least 35 vertices) is Hamiltonian one needs to require \(\delta(G)\geq{1\over 3}(n- 2)\).
Claw-free graph, Eulerian and Hamiltonian graphs, Extremal problems in graph theory, (Sub)pancyclic, subpancyclic, pancyclic, (Hamilton) cycle, Hamiltonian, Theoretical Computer Science, Circumference, claw-free graph, IR-74021, Discrete Mathematics and Combinatorics, METIS-140565, longest cycle, Paths and cycles
Claw-free graph, Eulerian and Hamiltonian graphs, Extremal problems in graph theory, (Sub)pancyclic, subpancyclic, pancyclic, (Hamilton) cycle, Hamiltonian, Theoretical Computer Science, Circumference, claw-free graph, IR-74021, Discrete Mathematics and Combinatorics, METIS-140565, longest cycle, Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
