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 know...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]）.展开更多
基金the National Natural Science Foundation of China(10671095)
文摘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]）.
