图的最小完整度

数学物理学报

图的最小完整度

马润年;刘乃功

西安交通大学理学院西安 710049

大连大学信息科学与工程辽宁省高校重点实验室大连 116622

收稿日期:2003-12-08 修回日期:2005-10-22 出版日期:2006-04-25 发布日期:2006-04-25
通讯作者: 马润年
基金资助:
中国博士后科学基金(2003033516)和大连大学信息科学与工程辽宁省高校重点实验室资助

Minimum Integrity of Graphs

Ma Runnian;Liu Naigong

School of Science, Xi'an Jiaotong University, Xi'an 710049
University Key Lab of Information Sciences and Engineering, Dalian University, Dalian 116622

Received:2003-12-08 Revised:2005-10-22 Online:2006-04-25 Published:2006-04-25
Contact: Ma Runnian

摘要/Abstract

摘要： 主要研究了图的完整度,并给出若干关于完整度的结果. 对于所有的顶点数和边数都给定的连通图类,如何确定该图类中完整度最小的图. 同时研究了对于顶点数和完整度都给定的连通图类,如何确定该图类中边数最多的图的问题. 这些结果为图的最小完整度的优化设计提供了理论和方法.

关键词: 图论, 完整度, 最小完整度

Abstract: The integrity of a graph is mainly studied and some results on the integrity are given. Given the number of vertices and the number of edges in a class of graphs, the problem of how to determine a graph that has the minimum integrity among the class is studied. Also, if the number of vertices and the integrity in a class of graphs are fixed, the problem of how to determine a graph that has the maximum number of edges among them is investigated. For the optimal designs of the minimal integrity, the theoretics and methods are provided.

Key words: Graph theory, Integrity, Minimum integrity

中图分类号:

05C70

马润年;刘乃功. 图的最小完整度[J]. 数学物理学报, 2006, 26(2): 251-257.

Ma Runnian;Liu Naigong. Minimum Integrity of Graphs[J]. Acta mathematica scientia,Series A, 2006, 26(2): 251-257.