• CARMA DISCRETE MATHEMATICS INSTRUCTIONAL SEMINAR
  • Speaker: Mr Ramiro Feria Purón, School of Electrical Engineering and Computer Science, The University of Newcastle
  • Title: On bipartite graphs of defect 4
  • Location: Room V111, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Thu, 12th Jul 2012
  • Abstract:

    We consider the bipartite version of the degree/diameter problem; namely, find the maximum number Nb(d,D) of vertices in a bipartite graph of maximum degree d>2 and diameter D>2. The actual value of Nb(d,D) is still unknown for most (d,D) pairs.

    The well-known Moore bound Mb(d,D) gives a general upper bound for Nb(d,D); graphs attaining this bound are called Moore (bipartite) graphs. Moore bipartite graphs are very scarce; they may only exist for D=3,4 or 6, but no other diameters. Interest has then shifted to investigate the existence or otherwise of graphs missing the Moore bound by a few vertices. A graph with order Mb(d,D)-e is called a graph of defect e.

    It has been proved that bipartite graphs of defect 2 do not exist when D>3. In our paper we 'almost' prove that bipartite graphs of defect 4 cannot exist when D>4, thereby establishing a new upper bound on Nb(d,D) for more than 2/3 of all (d,D) combinations.


  • [Permanent link]