Long cycles and 3-connected spanning subgraphs of bounded degree in 3- connected \(K_{1,d}\)-free graphs
type: Item
instance of: scholarly article
title: Long cycles and 3-connected spanning subgraphs of bounded degree in 3- connected \(K_{1,d}\)-free graphs
zbMATH Open document ID: 0821.05035
author: Nicholas Wormald
author: Bill Jackson
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-07-02T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 767688
zbMATH Keywords: long cycles
zbMATH Keywords: bounded degree
zbMATH Keywords: \(k\)-connected graph
zbMATH Keywords: maximum degree
zbMATH Keywords: spanning subgraph
reviewed by: R. C. Entringer
MaRDI profile type: Publication
full work available at URL: jctb.1995.1013
OpenAlex ID: W2036217110
DOI: 10.1006/JCTB.1995.1013
Recommended article: Q4388360
Recommended article: Long cycles in graphs with no subgraphs of minimal degree 3
Recommended article: Long cycles in 3-connected graphs
Recommended article: Q4294581
Recommended article: Q3136994
Recommended article: Long cycles in 3-cyclable graphs
Recommended article: Cycles of given length in some \(K_{1,3}\)-free graphs
Recommended article: Longest paths and cycles in K1,3-free graphs
Recommended article: Long cycles in triangle-free graphs with prescribed independence number and connectivity
Recommended article: Q4542177
description: scientific article; zbMATH DE number 767688