科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let r, s be positive integers with r > s, k a nonnegative integer and n = 2r - s + k. A uniform subset graph G(n, r, s) is a graph with vertex set vertical bar n vertical bar(r) and where two r-subsets A. B epsilon vertical bar n vertical bar(r) are adjacent if and only if vertical bar A boolean AND B vertical bar = s. Let diam (G) denote the diameter of a graph G. In this paper, we prove the following results: (1) If k > 0, then diam(G(n,r,s)) = [r-s-1/s+k] + 1 if r >= 2s + k + 2, 2 if k >= s and 2s <= r <= s + k, or k < s and s + k <= r <= 2s, and 3 otherwise; (2) If k = 0, then diam(G(n,r,s)) = [r-1/s]. This generalizes a result in [M. Valencia-Pabon, J-C. Vera. On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].
- 出版日期2008-12-28
- 单位浙江师范大学
