• CARMA-GTA DISCRETE MATHEMATICS SEMINAR
  • Speaker: Prof Edy Tri Baskoro, Institut Teknologi Bandung (ITB)
  • Title: Necessary Conditions for the existence of Almost Moore Digraphs
  • Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Thu, 26th Sep 2013
  • Abstract:

    It is well known that the Moore digraph, namely a diregular digraph of degree d, diameter k and order 1 + d + d 2 + ... + d k , only exists if d = 1 or k = 1. Let (d,k)-digraph be a diregular digraph of degree d ≥ 2, diameter k ≥ 2 and order d+d 2 +...+d k , one less than the Moore bound. Such a (d,k)-digraph is also called an almost Moore digraph.

    The study of the existence of an almost Moore digraph of degree d and diameter k has received much attention. Fiol, Allegre and Yebra (1983) showed the existence of (d,2)-digraphs for all d ≥ 2. In particular, for d = 2 and k = 2, Miller and Fris (1988) enumerated all non-isomophic (2,2)-digraphs. Furthermore, Gimbert (2001) showed that there is only one (d,2)-digraph for d ≥ 3. However for de- gree 2 and diameter k ≥ 3, it is known that there is no (2,k)-digraph (Miller and Fris, 1992). Furthermore, it was proved that there is no (3,k)-digraph with k ≥ 3 (Baskoro, Miller, Siran and Sutton, 2005). Recently, Conde, Gimbert, Gonzáles, Miret, and Moreno (2008 & 2013) showed that no (d,k)-digraphs exist for k = 3,4 and for any d ≥ 2. Thus, the remaining case still open is the existence of (d,k)- digraphs with d ≥ 4 and k ≥ 5.

    Several necessary conditions for the existence of (d,k)-digraphs, for d ≥ 4 and k ≥ 5, have been obtained. In this talk, we shall discuss some necessary conditions for these (d,k)-digraphs. Open problems related to this study are also presented.


  • [Permanent link]