|
|||||
|
|
| 实现同一度序列的图的最大团数 | |
| 引用本文： | 尹建华,李炯生,陈国良.实现同一度序列的图的最大团数[J].运筹学学报,2006,10(3):66-72. |
| 作者姓名： | 尹建华 李炯生 陈国良 |
| 作者单位： | 1. 海南大学信息科学技术学院,海口,570228 2. 中国科学技术大学数学系,合肥,230026 3. 中国科学技术大学计算机系,合肥,230027 |
| 基金项目： | Supported by National Natural Science Foundation of China(No.10401010). |
| 摘 要： | 图G中最大完全子图的阶数称为G的团效．ω(π)和γ(π)分别表示实现度序列π=(d_1,d_2,…,d_n)的图的最大团数和最小团数．Erds,Jacobson和Lehel开始考虑确定具有相同度序列π的图的可能的团数问题．他们证明了对于充分大的n,有ω(π)-γ(π)-n一2n~(2/3)．在本文中,我们首先估计了一类特殊可图序列的ω(π)之值,其次我们建立了一个估计任意可图序列π的ω(π)之值的算法． |
| 关 键 词： | 运筹学 图 度序列 团数 |
| 收稿时间： | 2002-05-24 |
| 修稿时间： | 2002年5月24日 |
The Largest Clique Number for Graphs Realizing the Same Degree Sequence |
|
| Yin Jianhua,Li Jiongsheng,Chen Guoliang.The Largest Clique Number for Graphs Realizing the Same Degree Sequence[J].OR Transactions,2006,10(3):66-72. | |
| Authors: | Yin Jianhua Li Jiongsheng Chen Guoliang |
| Institution: | College of Information Science and Technology, Hainan University, Haikou 570228, China;Department of Mathematics, University of Science and Technology of China, Hefei 230026, China;Department of Computer Science, University of Science and Technology of China, Hefei 230027, China |
| Abstract: | The order of the largest complete subgraph in graph G is called the clique number of G. We write ω(π) and γ(π) to denote the largest clique number and the smallest clique number for graphs realizing the same degree sequence π = (d1, d2,… ,dn), respectively.Erdos, Jacobson and Lehel1] began considering the question of the possible clique number attained by graphs with the same degree sequence π. They showed that ω(π) - γ(π) is approximately n - 2n2/3, for sufficiently large n. In this paper, we estimate the values ω(π) for a special class of graphic sequences, which enables us to found an algorithm to estimate the value ω(π) for any graphic sequence π. |
| Keywords: | Operation research graph degree sequence clique number |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |