连通[5,3]-图的最长路(圈)

The longest paths(Cycles) in [5,3]-graphs

如果G中任意s个点的导出子图中至少含有t条边,则称G为[s,t]图.文中证明了:阶数不小于6的连通[5,3]图的最长路的长度不小于n-2,且路长的界是紧的,其最长圈的长度可任意小.

A graph G is called[s,t]-graph, if there are at least t edges in every included subgraphs of s vertices. In this paper ,we show the following results： （1）If G is a connected [5,3]-graph and IGI ≥6,then the longest path of G is of length at least n-2. Moreover,n-2 is the best possible; （2） If G is a connected [5,3]-graph and IGI≥6, then the longest cycle of G is indefinte.