The (Delta,D,D,1) Problem for Graphs

Under Construction !

The (Delta, D,D', s)-problem asks for the largest graphs of maximum degree Delta 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=Delta -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 (Delta, D, D, 1)-problem. A bound on the order of a (Delta, D, D, 1) graph can be obtained as follows. In any (Delta, 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 Delta paths of length 1, at most Delta(Delta-1) paths of length 2 and in general at most Delta(Delta-1)^{k-1} paths of length k, the maximum order of a (Delta, 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 (Delta, 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 (Delta, 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).

LARGEST KNOWN (Delta, D, D, 1)-GRAPHS (Feb. 95)
Delta\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

References

  1. 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.
  2. 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.
  3. J-C Bermond, N. Homobono \& C. Peyrat, Large fault-tolerant interconnection networks, Graphs and Combinatorics (1989) 107-123.
  4. J. Bond, Construccions de grands r\'eseaux d'interconnexion, Th\`ese de 3-i\`{eme cycle, LRI (1984).
  5. J. Bond, Construccions de grands r\'eseaux d'interconnexion, These d'etat. LRI (1987).
  6. J. Bond \& C. Peyrat, Diameter vulnerability in networks, Graph Theory with Application to Algorithms and Computer Science, Wiley Interscience (1985) 123-149.
  7. 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.
  8. J. G\'omez, Diametro y vulnerabilidad en redes de interconexi\'on, Doctoral Thesis, Barcelona (1986).
  9. J. G\'omez, Some $(\Delta, D,D,1)$ graphs, Report of investigation, E.T.S.I.T., Barcelona (1994).
  10. J. G\'omez \& M.A.Fiol, Dense compound graphs, Ars Combinatoria, 20-A (1985) 211-235.
  11. J. G\'omez \& J.L.A.Yebra, $(\Delta, D,D,1)$ compound graphs, Report of investigation, E.T.S.I.T., Barcelona (1994).
  12. J. G\'omez \& J.L.A.Yebra, On $(\Delta, D,D+1,1)$ problem, Report of investigation, E.T.S.I.T., Barcelona (1994).
  13. W.H. Kautz, Design of optimal interconnection networks for multiprocessor, Architecture and Design of Digital Computer. Nato advanced Institute (1969), 249-272.
  14. J.G. Kuhl. \& S.M. Reddy, Fault-tolerance considerations in large multiprocessor systems, IEEE Computer (1986), 56-67.
  15. C. Peyrat, Vulnerabilit\'e dans les r\'eseaux d'interconnexion, Th\`ese de 3-i`{eme cycle, LRI (1984).
  16. C. Peyrat, Diameter vulnerability of graphs, Discr. Appl. Math. (1984), 245-250.
  17. C. Peyrat, Les reseaux d'interconnexion et leur vulnerabilit\'e These d'etat. LRI (1987).
  18. J.J. Quisquater, Structures d'interconnexion: Constructions et applications, These d'etat. LRI (1987).
  19. J.L.A. Yebra, Largest invulnerable graphs, Submitted to Journal of Graph Theory.
  20. 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.
  21. 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 (Delta,D) graph problem and (Delta,D) vertex symmetric digraph problem . We keep also the corresponding tables: