Long paths and cycles in tough graphs (Q2366213): Difference between revisions

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\).