| 阶数极大的临界全控制图 |
| |
| 引用本文： | 李凡,陆玫.阶数极大的临界全控制图[J].中国科学:数学,2011,41(12):1089-1094. |
| |
| 作者姓名： | 李凡 陆玫 |
| |
| 作者单位： | 香港中文大学计算机科学与工程系, 香港;
清华大学数学科学系, 北京100084 |
| |
| 基金项目： | 国家自然科学基金（批准号：10971114 10990011 11171097）资助项目 致谢 作者对审稿人的有益建议深表感谢. |
| |
| 摘 要： | 称一个没有孤立点的图G 为临界全控制图, 如果G 满足对于任何一个不与悬挂点相邻的顶点v, G - v 的全控制数都小于G 的全控制数. 如果G 的全控制数记为γt, 则称这样的临界全控制图G 为γt- 临界的. 如果G 是γt- 临界的, 且阶数为n, 则n ≤ Δ(G)(γt(G)- 1) + 1, 其中Δ(G) 是G 的最大度. 本文将证明对γt = 3, 这个阶数的上界是紧的, 并给出所有满足n = Δ(G)(γt(G)- 1) + 1 的3-γt- 临界图.
|
| 关 键 词： | 全控制 点临界 最大度 |
Total domination critical graphs with maximal order |
| |
| LI Fan ＆ LU Mei.Total domination critical graphs with maximal order[J].Scientia Sinica Mathemation,2011,41(12):1089-1094. |
| |
| Authors: | LI Fan ＆ LU Mei |
| |
| Institution: | LI Fan ＆ LU Mei |
| |
| Abstract: | A graph G without isolated vertices is total domination vertex critical, if for any vertex v of G that is not adjacent to a pendant vertex, the total domination number of G-v is less than the total domination number of G. We call these graphs γt-critical. If G is a γt-critical graph of order n, then it can be shown that n≤△（G）（γt（G）-1）＋1, where △（G） is the maximum degree of G. In this paper, we characterize the graphs in the case n≤△（G）（γt（G）-1）＋1 with γt（G） = 3. |
| |
| Keywords: | total domination vertex critical maximum degree |
| 本文献已被 维普 等数据库收录！ |
| 点击此处可从《中国科学:数学》浏览原始摘要信息 |
| 点击此处可从《中国科学:数学》下载免费的PDF全文 |
|
