至多有2个等长圈的简单图的最大边数  

The Maximum Possible Number of Edges in a Simple Graph with at Most Two Cycles Having the Same Length

作　　者：徐坚成[1] 施永兵[2] 

机构地区：[1]上海市教科院智力开发研究所 [2]上海师范大学数理信息学院,上海200234

出　　处：《上海师范大学学报（自然科学版）》2003年第3期26-32,共7页Journal of Shanghai Normal University(Natural Sciences)

基　　金：上海市高校科技发展基金(02DK08)

摘　　要：设Sn是具有n个顶点至多有2个等长圈的简单图的集合。若Sn中不存在图G’使|E(C’)|>|E(G)|,Ng称G是简单的最大图分布(2)图(简记为简单MCD(2)图)。用f~*(n,2)表示具有n个顶点的简单MCD(2)图的边数。作者证明了f~*(n,2)≥(n-l)+[1/2(11n-20)^(1/2)]且当3≤n≤10时等式成立。Let Sn be the set of simple graphs on n vertices in which at most two cycles have the same length. A graph C is said to be a simple maximum cycle distributed(2) graph (Simple MCD(2)-graph) if there does not exist a graph G1 in Sn such that I E( G') | > | E( G)| . Let f (n,2) be the number of edges in a simple MCD(2) - graph on n vertices. In this paper , we prove that f(n,2) > (n - 1) + [1/2,11n -20]for each integer n >3 , and the equality holds when

关 键 词：圈 简单图 MCD(2)图 边数 

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