A Generalization of Brown's Construction for the Degree/Diameter Problem

2015/12/30 by Ishida, Yawara
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1512.08961

Abstract

The degree/diameter problem is the problem of finding the largest possible number of vertices n_Δ,D in a graph of given degree Δ and diameter D. We consider the problem for the case of diameter D=2. William G Brown gave a lower bound of the order of (Δ,2)-graph. In this paper, we give a generalization of his construction and improve the lower bounds for the case of Δ=306 and Δ=307. One is (306,2)-graph with 88723 vertices, the other is (307,2)-graph with 88724 vertices.

Related

• Large Cayley graphs of small diameter
• New large graphs with given degree and diameter
• The Degree-Diameter Problem for Circulant Graphs of Degree 8 and 9
• Sharper Lower Bounds in the Maximum Degree and Diameter Bounded Subgraph Problem in the Mesh
• The degree-diameter problem for plane graphs with pentagonal faces