Long paths and cycles in tough graphs
type: Item
instance of: scholarly article
title: Long paths and cycles in tough graphs
zbMATH Open document ID: 0778.05047
DOI: 10.1007/BF01195323
published in: Graphs and Combinatorics
publication date: 1993-06-29T00:00:00Z
review text: Denote by \(p(G)\) \((c(G))\) the length of a longest path (cycle) in the graph \(G\). Let \(\pi(t,n)\) \((\gamma(t,n))\) be the minimum of \(p(G)\) \((c(G))\) over all \(t\)-tough \((t\)-tough and 2-connected) graphs of order \(n\). It is shown that if \(G\) is a noncomplete \(t\)-tough graph \((t>0)\) of order \(n\) then \[ p(G)+{1\over\log(1/t+1)}\log(p(G)+3)\geq{1\over\log(1/t+1)}(\log n+1). \] Also, if \(G\) is a \(t\)-tough \((t>0)\) 2-connected graph of order \(n\) then \[ \log c(G)+\left({1\over 2}c(G)-1\right)\log\left({1\over 2}c(G)- 1+t\right)-\left({1\over 2}c(G)-1\right)\log t\geq\log n. \] Bounds for \(\pi(t,n)\) and \(\gamma(t,n)\) are given. The authors conjecture that, for \(t>0\), \(\gamma(t,n)\geq A\log n\) for some constant \(A\) depending only on \(t\). Finally, generalizing a conjecture of \textit{J. A. Bondy} [Paths and cycles, in \textit{R. L. Graham}, \textit{M. Grötschel} and \textit{L. Lovász} (eds.), Handbook of combinatorics, to appear] for the case \(l=3\), it is shown that if \(G\) is a 2-connected \(K_{1,l}\)-free graph of order \(n\) then \(c(G)\geq{4\over\log(l-1)}\log n-A\) for some absolute constant \(A\).
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 223443
zbMATH Keywords: cycle
zbMATH Keywords: longest path
author: Hajo Broersma
author: Jan van den Heuvel
author: Heinz A. Jung
author: Henk Jan Veldman
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Relative lengths of paths and cycles in 3-connected graphs
cites work: Q3097395
cites work: Tough graphs and Hamiltonian circuits.
cites work: Some Theorems on Abstract Graphs
cites work: Toughness and the existence ofk-factors
cites work: Relative lengths of paths and cycles in k-connected graphs
cites work: Hamiltonian results inK1,3-free graphs
cites work: Q3997887
cites work: On a connection between the existence of k-trees and the toughness of a graph
full work available at URL: https://doi.org/10.1007/bf01195323
OpenAlex ID: W1981157645
description: scientific article