各等长圈数不超过2的简单图的最大边数  

The maximum possible number of edges in a simple graph in which at most two cycles have the same length

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

机构地区：[1]上海市公共行政与人力资源研究所,上海200031 [2]上海师范大学数理信息学院,上海200234

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

基　　金：上海市高校科技发展基金(04DB25)

摘　　要：设S_n是具有n个顶点各等长圈数不超过2的简单图的集合,若S_n中不存在图G′使|E(G′)|＞|E(G)|,则称G是简单的最大圈分布(2)图(简记为简单MCD(2)图),用f~*(n,2)表示具有n个顶点的简单MCD(2)图的边数,证明了对每个整数11≤n≤14,有f~*(n,2)=n+[1/2((11n-20)^(1/2)-2)],其中[a]是小于等于a的最大整数．Let Sn be the set of simple graphs on n vertices in which at most two cycles have the same length. A graph G is called a simple maximum cycle distributed （2） graph （ Simple MCD （ 2 ） -graph） if there does not exist a graph G＇ in S. such that ｜ E（G＇） ｜ 〉 ｜ E（G） ｜. Let f＇ （n,2） be the number of edges in a simple MCD（2） -graph on n vertices. We prove that f＊ （n,2） = n ＋ [1/2（ 1√11n - 20 - 2）] for any integer n satisfying 11 ≤ n ≤ 14, where [a] is the greatest integer which is less than or equal to a.

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

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