Heavy cycles in \(k\)-connected weighted graphs with large weighted degree sums (Q941397): Difference between revisions

A weighted graph is a graph in which each edge \(e\) is assigned a nonnegative weight \(w(e)\). The \textit{claw} is the bipartite graph \(K_{1,3}\). The \textit{paw} is obtained from the claw by adding one edge \(xy\) where \(x\) is not adjacent to \(y\) in \(K_{1,3}\). For a vertex \(v\), let \(N(v)\) be the set of vertices adjacent to \(v\), and \(d^w(v) = \sum_{x \in N(v)} w(vx)\). Also, let \(\sigma_k^w = \min \{ \sum_{ v \in S} d^w(v): S\) is a set of \(k\) pairwise nonadjacent vertices \(\}\). The weight of a cycle \(C\) is the sum of the weights of its edges. Improving the results of \textit{H. Enomoto, J. Fujisawa} and \textit{K. Ota} [Ars Comb. 76, 225--232 (2005; Zbl 1164.05389)], the authors provided new sufficient conditions for the existence of heavy cycles. They proved that for a \(k\)-connected weighted graph \(G\) with \(\sigma_{k+1}^w \geq m\), if all its edges have the same weight for each induced claw and each induced paw, then \(G\) contains a Hamiltonian cycle or a cycle of weight at least \(2m/(k+1)\).