A \(\sigma_k\) Type Condition for Heavy Cycles in Weighted Graphs

Abstract

A weighted graph is one in which every edge \(e\) is assigned a non-negative number, called the weight of \(e\). For a vertex \(v\) of a weighted graph, \(d^w(v)\) is the sum of the weights of the edges incident with \(v\). For a subgraph \(H\) of a weighted graph \(G\), the weight of \(H\) is the sum of the weights of the edges belonging to \(H\). In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. Let \(G\) be a \(k\)-connected weighted graph where \(2 \leq k\). Then \(G\) contains either a Hamilton cycle or a cycle of weight at least \(2m/(k+1)\), if \(G\) satisfies the following conditions:(1)The weighted degree sum of any \(k\) independent vertices is at least \(m\),(2) \(w(xz) = w(yz)\) for every vertex \(z \in N(x) \cap N(y)\) with \(d(z,y) = 2\), and (3)In every triangle \(T\) of \(G\), either all edges of \(T\) have different weights or all edges of \(T\) have the same weight.