Long cycles and 3-connected spanning subgraphs of bounded degree in 3- connected \(K_{1,d}\)-free graphs (Q1892839)

Let \(f_{k, d}(n)\) denote the largest integer \(m\) such that every \(k\)- connected graph on \(n\) vertices with maximum degree \(d\) contains a cycle of length at least \(m\), and \(g_{k, d}(n)\) denote the largest integer \(m\) such that every \(k\)-connected \(K_{1,d+ 1}\)-free graph on \(n\) vertices contains a cycle of length at least \(m\). Then \(f_{k, d}(n)\geq g_{k,d}(n)\). \textit{J. A. Bondy} and the reviewer [Can. J. Math. 32, 1325-1332 (1980; Zbl 0409.05037)] showed \(f_{2, d}\sim 4\log_{d- 1} n\) and the authors in [Longest cycles in 3-connected graphs of bounded maximum degree, Lect. Notes Pure Appl. Math. 139, 237-254 (1992; Zbl 0790.05048)] proved \(c_ 1 n^{c_ 2}\geq f_{3, d}(n)\geq n^{c_ 3}/2\) for specified constants \(c_ 1\), \(c_ 2\) and \(c_ 3\). \textit{J. A. Bondy} [Basic graph theory: paths and circuits, in ``Handbook of combinatorics'' (R. L. Graham, M. Grötschel and L. Lovasz, eds.), North Holland, Amsterdam, 1995, to appear] asked if analogous results hold for \(g_{2, 2}(n)\) and \(g_{3, 2}(n)\). \textit{H. J. Broersma}, \textit{J. van den Heuvel}, \textit{H. A. Jung} and \textit{H. J. Veldman} [Graphs Comb. 9, No. 1, 3-17 (1993; Zbl 0778.05047)] showed \(g_{2, d}(n)\geq c_ 4+ 4\log_ d n\) for a constant \(c_ 4\) and for all \(d\geq 2\). Here the authors prove \(g_{3, d}(n)\geq n^{c_ 5}/2\), where \(c_ 5= 1/(\log_ 2 6+ 2\log_ 2(2d+ 1))\), for all \(d\geq 1\). The arguments of Broersma et al. and the present authors depend on the following conjecture: There exists a function \(h(d, k)\) such that every \(k\)- connected \(K_{1, d}\)-free graph has a \(k\)-connected spanning subgraph with maximum degree at most \(h(d, k)\).