Journal of University of Science and Technology of China ›› 2013, Vol. 43 ›› Issue (8): 603-606.DOI: 10.3969/j.issn.0253-2778.2013.08.001

    Next Articles

The wide-diameter of regular graphs

LI Jiaao   

  1. School of Mathematical Sciences, University of Science and Technology of China; Wu Wentsun Key Laboratory of Mathematics, USTC, Chinese Academy of Sciences, Hefei 230026, China
  • Received:2012-12-20 Revised:2013-05-22 Online:2013-08-31 Published:2013-08-31
  • Contact: XU Junming
  • About author:LI Jiaao, male, born in 1990, master. Research field: Combinatorics and graph theory. E-mail: lijiaao@mail.ustc.edu.cn

Abstract: The diameter with width m of a graph G is defined as the minimum integer d for which between any two distinct vertices in G there exist at least m internally disjoint paths of length of at most d. It was shown that the tight upper bound on m-diameter of w-regular w-connected graph with order n is(n-2)(w-2)[](w-m+1)(3m-w-4)+1 for any integer m with 2w+5[]3≤m≤w. Some known results can be deduced or improved from the obtained result.

Key words: graphs, connectivity, diameter, wide-diameter, regular graphs, networks, fault tolerance