The number of cycle lengths in graphs of given minimum degree and girth
Let \(n(g,k)\) be the minimum number of different cycle lengths in a graph of given minimum degree \(k\) and girth \(g\). The paper gives lower bounds for \(n(g,k)\). The most general lower bound is \(ck^{g/8}\). For particular values of \(g\) better lower bounds are given: \(n(5,k)\geq (k^2+ k-2)/4\), \(n(9,k)\geq c_1k^3\), \(n(7,k)\geq c_2 k^{5/2}\), and for \(t\geq 2\), \(n(4t- 1,k)\geq c_3 k^{t/2}\). The lower bound for \(n(5,k)\) is the best possible within a constant multiplicative factor, the other lower bounds are likely far from the truth.
- Ranking hypotheses to minimize the search cost in probabilistic inference models
- Estimations for the number of cycles in a graph
- Cycle lengths in expanding graphs
- Cycle lengths modulo k in expanders
- The lattice of cycles of an undirected graph
- Circumference, chromatic number and online coloring
- On the distribution of cycle lengths in graphs
- scientific article; zbMATH DE number 151768 (Why is no real title available?)
- Cycle spectra of Hamiltonian graphs
- On the Number of Cycles in a Graph with Restricted Cycle Lengths
- Cycles of many lengths in Hamiltonian graphs
- Cycles in graphs of fixed girth with large size
- Some extremal problems on the cycle length distribution of graphs
- Number of cycles of small length in a graph
- A simple proof for the lower bound of the girth of graphs \(D(n,q)\)
- Girth in graphs
- Cycle lengths in sparse graphs
This page was built for publication: The number of cycle lengths in graphs of given minimum degree and girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1301632)
