Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777043 | Discrete Mathematics | 2017 | 12 Pages |
Abstract
Let Î be a distance-regular graph with valency k and diameter D, and let x be a vertex of Î. We denote by ki(0â¤iâ¤D) the number of vertices at distance i from x. In this paper, we try to quantify the difference between antipodal and non-antipodal distance-regular graphs. We will look at the sum kDâ1+kD, and consider the situation where kDâ1+kDâ¤2k. If Î is an antipodal distance-regular graph, then kDâ1+kD=kD(k+1). It follows that either kD=1 or the graph is non-antipodal. And for a non-antipodal distance-regular graph, it was known that kD(kDâ1)â¥k and kDâ1â¥k both hold. So, this paper concerns on obtaining more detailed information on the number of vertices for a non-antipodal distance-regular graph. We first concentrate on the case where the diameter equals three. In this case, the condition kD+kDâ1â¤2k is equivalent to the condition that the number of vertices is at most 3k+1. And we extend this result to all diameters. We note that although the result of the diameter 3 case is a corollary of the result of all diameters, the main difficulty is the diameter 3 case, and that the diameter 3 case confirms the following conjecture: there is no primitive distance-regular graph with diameter 3 having the M-property.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jongyook Park,