| 变换图的直径及Brualdi猜想 |
| |
| 引用本文： | 钱建国.变换图的直径及Brualdi猜想[J].数学学报,2002,45(2):411-416. |
| |
| 作者姓名： | 钱建国 |
| |
| 作者单位： | 厦门大学数学系,福建,厦门,361005 |
| |
| 基金项目： | 厦门大学博士自选课题资助项目（Y07001） |
| |
| 摘 要： | 设Ｒ＝（ｒ１，ｒ２…ｒｍ）及 Ｓ＝（Ｓ１，Ｓ２，…，Ｓｎ）为两个正整数向量，满足Σｍｉ＝１ｒｉ＝Σｎｊ＝１ｓｊ＝ Ｋ．记Ｇ（Ｒ，Ｓ）为（０，１）－矩阵类 Ｕ（Ｒ，Ｓ）的变换图．Ｂｒｕａｌｄｉ在文山中给出了 Ｇ（Ｒ，Ｓ）的直径厂（Ｇ（Ｒ，Ｓ））的一个上界：ｍｎ／２－１，并猜想Ｄ（Ｇ（Ｒ，Ｓ））≤ｍｎ／４．本文通过对有向图围长的研究得到了Ｄ（Ｇ（Ｒ，Ｓ））的一个新的上界：１／２ｍｎ－１／６ｔ（ｔ－１）（４ｔ＋１），其中Ｔ＝ ．
|
| 关 键 词： | 变换图 直径 有向图 有向圈 围长 |
| 文章编号： | 0583-1431(2002)02-0411-06 |
| 修稿时间： | 1997年11月24 |
The Diameter of Interchange Graphs and the Brualdi's Conjecture |
| |
| QIAN Jian Guo.The Diameter of Interchange Graphs and the Brualdi''''s Conjecture[J].Acta Mathematica Sinica,2002,45(2):411-416. |
| |
| Authors: | QIAN Jian Guo |
| |
| Institution: | QIAN Jian Guo (Department of Mathematics. Xiamen University, Xiamen 361005, P. R. China) |
| |
| Abstract: | Let R = (r1, r2，…，rm) and S = (s1, s2,..., sn) be two nonnegative integral vectors with Σmi=1ri=Σnj=1sj=K. Denote by G(R. S) the interchange graph of the class U(R, S) of (0,1)-matrices. Brualdi proved that the diameter of G(R, S) is less than mn/2 - 1, and further conjectured that it is no more than mn/4. In this paper, by studying the girth of the directed graphs, a new upper bound of the diameter of G(R, S) is proved to be 1/2mn - 1/6t(t - 1)(4t + 1), where t = mn/(m + n). |
| |
| Keywords: | Interchange graph Diameter Digraph Dicycle Girth |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《数学学报》浏览原始摘要信息 |
| 点击此处可从《数学学报》下载免费的PDF全文 |
|
