| Minimum Diameter Orientations of Km∨Kn |
| |
| 作者姓名： | MIAO Xiao-yan SUN Zhi-ren |
| |
| 作者单位： | [1]Shanghai Gaoqiao High School, Shanghai 200137, China; [2]School of Mathematics and Computer Science, Nanjing Normal University, Nanjing 210097, China |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China（10671095） .Acknowledgements The authors are grateful to Professor Huang Jing of Victoria University for his useful comments and suggestions. |
| |
| 摘 要： | For a graph G, let D denote an orientation of G having minimum diameter. Define f（G） =diamD. In this paper, we concentrate on exploring the minimum diameter of Km ∨ Kn（m ≥ 1, n ≥ 1）. Some special cases are known： f（Km ∨ Kn） = ∞, 2, 3, where m = landn ≥ 1, m = 2 or m ≥ 4 andn = 1, m=3 and n = 1, respectively. So we only consider the case when m ≥ 2 and n ≥ 2. The following results are obtained. （1） f（Km ∨ Kn） = 3, where m = 2, 3, n ≥ 2 and m = n = 4. （2） f（Km ∨ Kn） = 2, m where m ≥ 5 andmisodd, 2 ≤ n ≤ （m[m/2]）-m. （3） f（Km ∨ Kn） = 2, whereto ≥ 4 and m≡ 0（rood4）, 2 ≤ n ≤ （m m/2）-（m/2＋1）. （4） ]（Km ∨ Kn） = 2, where m ≥ 6 and m ≡ 2（mod4）, 2 ≤ n ≤ （m m/2）-m/2. （5）/（Km ∨ Kn） = 3, where m ≥ 4, n 〉 （m[m/2]）.
|
| 关 键 词： | 最小直径 定向 Km∨Kn 图论 |
| 文章编号： | 1002-0462（2007）03-0359-05 |
| 收稿时间： | 2004-12-01 |
| 本文献已被 维普 等数据库收录！ |
|
