Long cycles in graphs with large degree sums (Q749553): Difference between revisions

Let G be an undirected graph on n vertices with no loops or multiple edges. The number of components of G and the independence number of G are denoted by \(\omega\) (G) and \(\alpha\) (G), respectively. G is t-tough if \(| S| \geq t\omega (G-s)\) for any subset S of V(G) with \(\omega (G-S)>1\). A cycle C of G is a dominating cycle if every edge of G has at least one of its vertices on C. Let \(d(x)+d(y)+d(z)\geq s\) for all triples of independent vertices x, y and z of G. The authors prove a number of results concerning long cycles in graphs with large degree sums. In particular, if c denotes the length of the longest cycle in G they prove: 1. If G is 1-tough and \(s\geq n\), then every longest cycle in G is a dominating cycle and \[ c\geq \min \{n,n+\frac{1}{3}s-\alpha \}\geq \frac{1}{6}n. \] 2. If G is 2-connected and \(s\geq n+2\), then \[ c\geq \min \{n,n+\frac{1}{3}s-\alpha \}. \]