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