The *(, D,D', s)-problem* asks for the largest graphs of maximum degree and
diameter *D* such that the subgraphs obtained by deleting any set of up to *s*
vertices have diameter less or equal than *D'*. The cases *s=1* and *D'-D=0,1,2* have been studied, see [1,3,4,5,6,8,16,19].
The case *s= -1* has been studied in [19,21]. The increase in the
diameter caused by edge deletion has also been studied, see [3].
In this document we deal with the *(, D, D, 1)-problem*. A bound on the
order of a *(, D, D, 1) graph* can be obtained as follows. In any
(, D, D, 1)-graph, any pair of non-adjacent vertices must be joined by
at least *s+1=2* different paths of length less or equal than *D*. Since from any vertex
there are at most paths of length 1, at most (-1)
paths of length 2 and in general at most *(-1)^{k-1}* paths of
length *k*, the maximum order of a (, D, D, 1)-graph is bounded by
It is shown in [19] that this bound cannot
be achieved for D greater or equal than 3.
In this context, it is of great interest to find (, D, D, 1)-graphs which
for a given diameter and maximum degree have a number of vertices
as close as possible to this bound.

The following table gives the

**LARGEST KNOWN (, D, D, 1)-GRAPHS**

as in
*February 1995*. Click the position you wish to know the
details: graph description, author, bibliography...P>
Send new results to `comellas@mat.upc.es` (Francesc Comellas, DMAT, keeper of this WWW table).

\D | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|

2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

3 | 6 | 12 | 18 | 34 | 52 | 102 | 124 | 172 | 172 |

4 | 10 | 21 | 55 | 68 | 203 | 203 | 512 | 1152 | 1538 |

5 | 16 | 34 | 126 | 146 | 320 | 548 | 2912 | 4368 | 9120 |

6 | 20 | 48 | 126 | 462 | 975 | 2917 | 10920 | 26225 | 78735 |

7 | 24 | 72 | 126 | 462 | 1716 | 5460 | 31248 | 62496 | 163800 |

8 | 30 | 100 | 324 | 1281 | 5124 | 20481 | 81924 | 327681 | 1310724 |

9 | 32 | 150 | 384 | 1536 | 6141 | 31248 | 156864 | 392160 | 2437344 |

10 | 48 | 200 | 755 | 3751 | 18875 | 93751 | 588240 | 2941200 | 12235392 |

11 | 50 | 250 | 815 | 4051 | 22255 | 156864 | 823536 | 3647088 | 31372800 |

12 | 64 | 300 | 1518 | 9073 | 54438 | 326593 | 2790060 | 16607500 | 116584050 |

13 | 66 | 370 | 1728 | 10368 | 62208 | 531440 | 3720080 | 22719060 | 217890400 |

14 | 100 | 455 | 2751 | 19209 | 134463 | 941193 | 9920736 | 65547720 | 581071680 |

15 | 102 | 546 | 2919 | 20385 | 142695 | 1417248 | 12755232 | 96727176 | 1037425536 |

- J-C Bermond, J. Bond, M. Paoli \& C. Peyrat, Graphs and interconnection networks, diameter and vulnerability, London Mathematical Society Lecture Notes Series 82 (Cambridge Uni. Press, Cambridge, 1983) 1-30.
- J-C Bermond, C. Delorme \& J.J. Quisquater, Grands graphes non dirig\'{es de degr\'{e et diam\`{etre fixés, Ann. Dicrete Math. 17 (1982) 65-67.
- J-C Bermond, N. Homobono \& C. Peyrat, Large fault-tolerant interconnection networks, Graphs and Combinatorics (1989) 107-123.
- J. Bond, Construccions de grands r\'eseaux d'interconnexion, Th\`ese de 3-i\`{eme cycle, LRI (1984).
- J. Bond, Construccions de grands r\'eseaux d'interconnexion, These d'etat. LRI (1987).
- J. Bond \& C. Peyrat, Diameter vulnerability in networks, Graph Theory with Application to Algorithms and Computer Science, Wiley Interscience (1985) 123-149.
- M.A. Fiol, J.L.A. Yebra \& I. Alegre, Line digraph iterations and the (d,k) problem, IEEE Trans. on Comp. c-33 n.5 (May~1984) 400-403.
- J. G\'omez, Diametro y vulnerabilidad en redes de interconexi\'on, Doctoral Thesis, Barcelona (1986).
- J. G\'omez, Some $(\Delta, D,D,1)$ graphs, Report of investigation, E.T.S.I.T., Barcelona (1994).
- J. G\'omez \& M.A.Fiol, Dense compound graphs, Ars Combinatoria, 20-A (1985) 211-235.
- J. G\'omez \& J.L.A.Yebra, $(\Delta, D,D,1)$ compound graphs, Report of investigation, E.T.S.I.T., Barcelona (1994).
- J. G\'omez \& J.L.A.Yebra, On $(\Delta, D,D+1,1)$ problem, Report of investigation, E.T.S.I.T., Barcelona (1994).
- W.H. Kautz, Design of optimal interconnection networks for multiprocessor, Architecture and Design of Digital Computer. Nato advanced Institute (1969), 249-272.
- J.G. Kuhl. \& S.M. Reddy, Fault-tolerance considerations in large multiprocessor systems, IEEE Computer (1986), 56-67.
- C. Peyrat, Vulnerabilit\'e dans les r\'eseaux d'interconnexion, Th\`ese de 3-i`{eme cycle, LRI (1984).
- C. Peyrat, Diameter vulnerability of graphs, Discr. Appl. Math. (1984), 245-250.
- C. Peyrat, Les reseaux d'interconnexion et leur vulnerabilit\'e These d'etat. LRI (1987).
- J.J. Quisquater, Structures d'interconnexion: Constructions et applications, These d'etat. LRI (1987).
- J.L.A. Yebra, Largest invulnerable graphs, Submitted to Journal of Graph Theory.
- J.L.A. Yebra, M.A. Fiol \& I. Alegre, Some large graphs with given degree and diameter, Journal of Graph Theory, vol. 110, (1986) 219-224.
- J.L.A. Yebra, V.J. Rayward-Smirh, \& A.P. Revitt, The $(\Delta,d,d',\Delta -1)$-problem with applications to computer networks Journal of Oper. Res. 33 (1991) 113-124.

Related problems are the so called (,D)