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

Longest Cycles in [5,3]-Graphs

作　　者：李宝杰 温如凤 李敏[2] 

机构地区：[1]山东泰安72707部队 [2]山东师范大学数学科学学院

出　　处：《科学技术与工程》2007年第22期5867-5868,共2页Science Technology and Engineering

摘　　要：如果G中任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图。现证明以下定理:设G是n(≥7)阶连通[5,3]-图,则G中最长圈的长度不小于[n/2],此界是最好可能的。A graph G is called [ s, t ]- graph, if there are at least t edges in every included subgraphs of s vertices. The following results is given： If G is a conneted [5,3 ] - graph and ｜G｜ ≥7, then the longest cycle of G is of length at least [ n/2 ]. Moreover, [ n/2 ] is the best possible.

关 键 词：[s t]图 最长路(圈) 路(圈)的长度 Hamilton路(圈) 

分 类 号：O157.5[理学—数学]