Bermond 1983 graphs interconnection networks diameter vulnerability

../

conjecture_p13: The 1983 survey's edge version of the degree–diameter problem: the largest number of edges of a graph with maximum degree r whose line graph has diameter at most D, the blown-up five-cycle giving 5r²/4 for D = 2 and even r, the survey's conjecture that this is the maximum, reported as proved by Kleitman in a private communication, and the general lower bound liminf n(2, D, r) r^{-D} ≥ (1/2)^{D−1}.

---

Bermond, J.-C. and Bond, J. and Paoli, M. and Peyrat, C., Graphs and interconnection networks: diameter and vulnerability. (1983), 1--30. The venue, which the site's reference text omits, is given by the papers that cite the survey (Chung, Gyárfás, Tuza and Trotter 1990; Faudree, Gyárfás, Schelp and Tuza 1989): Surveys in Combinatorics 1983 (Proceedings of the Ninth British Combinatorial Conference), London Mathematical Society Lecture Note Series 82, Cambridge University Press (1983), 1--30, doi:10.1017/CBO9781107325548.002 (Crossref chapter record).

Copy read. The copy read for this card is the HAL deposit hal-02447135 of the typescript: 17 PDF pages, a cover page, the first typescript page alone and upright on PDF p. 2, and then a two-up scan with two typescript pages per PDF page, rotated (PDF p. 17 carries only the last page, on the right), without a usable text layer beyond the cover and without printed page numbers; locators below give the PDF page and the left- or right-hand typescript page, and everything quoted was read on the rendered page images. The deposit prints "HAL Authorization" on its HAL cover sheet (PDF p. 1), and the HAL record hal-02447135 (publisher field Cambridge University Press; its API entry read 2026-10-02, its web page refusing access that day) gives as its license HAL's own authorization, the depositor's permission for HAL to distribute the deposit, with no Creative Commons line and no public reuse grant, every other right reserved.

Read status: claims checked for the "Case $\Delta=2$" passage of Section 6 (PDF p. 13, left- and right-hand typescript pages) and the Kleitman entry of the reference list (PDF p. 16; the list begins on PDF p. 14), read clause by clause on the page images on 2026-09-19; the rest of the digest records the import's reading of the page images, which was not repeated here.

This is a 30-page survey, not a research paper, organized in six sections: introduction, (Delta,D)-graphs, connectivity, disjoint paths, diameter vulnerability and extremal problems, and hypergraphs. Section 2 sets out the degree-diameter problem posed by Elspas: how many vertices n(Delta,D) can a graph of maximum degree Delta and diameter at most D have, records the Moore bound n(Delta,D) <= (Delta(Delta-1)^D - 2)/(Delta-2) for Delta>=3, the classification of Moore graphs (Delta=2 cycles, D=1 cliques, D=2 with Delta=3 the Petersen graph, and so on), and the bipartite analog n_1(Delta,g) = (2(Delta-1)^D - 2)/(Delta-2) for even girth. Section 4 covers graphs with many disjoint paths, Elspas's problem of the maximum order of a graph of maximum degree Delta in which every pair of vertices is joined by mu edge-disjoint paths of length at most k, and geodetic and strongly geodetic graphs. Section 5 collects diameter vulnerability results - Plesník's bound that deleting an edge from a graph of diameter D leaves it disconnected or of diameter at most 2D, the Chung-Garey generalization to s deleted edges with diameter at most (s+1)D + O(s) when the remaining graph is connected, (Delta,D,D',s)-graphs, the Murty-Vijayan extremal functions f_v(n,D,D',s) and f_e for graphs that keep small diameter after deletions, and diameter-critical graphs including the conjecture of Plesník, Murty and Simon bounding by floor(n^2/4) the edges of an n-vertex diameter-2 graph in which deleting any edge increases the diameter, with the Caccetta-Häggkvist bound (1/12)(1+sqrt 5)n^2 < 0.27n^2. Section 6 does the same for hypergraphs, giving the Moore-type bound n(Delta,D,r) <= 1 + Delta(r-1) sum_{i=0}^{D-1} (Delta-1)^i (r-1)^i. Its bearing on Problem 934, which asks to estimate the least number h_t(d) of edges forcing a graph of maximum degree at most d to contain two edges whose connecting path has length at least t, is through this bounded-degree bounded-diameter machinery: the survey's (Delta,D)-graph and Moore-bound material is the extremal degree-diameter framework in which such a bound sits, and, more directly, through the "Case $\Delta=2$" passage of Section 6 (PDF p. 13, left- and right-hand typescript pages, page images; paged at conjecture_p13), which the import's reading had not located: the dual of a $(2,D,r)$-hypergraph is a graph, so $n(2,D,r)$ is the largest number of edges of a graph of maximum degree $r$ and line diameter $D$, that is $h_D(r)-1$; the graph $C_5\otimes S_t$ gives $n(2,2,r)\ge\frac54r^2$ for even $r$; "answering one of our conjectures, it has been shown by Kleitman (1983) that every graph of maximum degree $r$ and line diameter $2$ has at most $\frac54r^2$ vertices. Thus $n(2,2,r)\le\frac54r^2$ and if $r$ is even $n(2,2,r)=\frac54r^2$" (the hypergraph's vertices are the graph's edges); and for general $D$, $\liminf_{r\to\infty}n(2,D,r)r^{-D}\ge(\frac12)^{D-1}$ from Benson's and Delorme's bipartite graphs, with $v_3,v_4,v_6\ge1$. The reference list, PDF p. 16 (the list begins on PDF p. 14), prints "Kleitman, D.J. (1983). Private communication of Trotter, W.T."

Source: https://inria.hal.science/hal-02447135v1.

Bears on. #934: Section 6, "Case $\Delta=2$" (PDF p. 13, left- and right-hand typescript pages; page images; paged at conjecture_p13): the edge version of the degree--diameter problem in the survey's own words, the construction $C_5\otimes S_t$ with $5t^2$ edges and line diameter $2$, the conjecture $n(2,2,r)\le\frac54r^2$ reported as proved by Kleitman (private communication of Trotter), so that $h_2(r)=\frac54r^2+1$ for even $r$, and the general lower bound $v_D\ge(\frac12)^{D-1}$; the site's key BBPP83 and its "Bermond, Bond, Paoli, and Peyrat [BBPP83] independently conjectured that $h_2(d)\le\frac54d^2+1$".

Results to transcribe.

• Edge version of the degree-diameter problem, Section 6, Case $\Delta=2$ (PDF p. 13, left- and right-hand typescript pages, page images): $n(2,D,r)$ equals the maximum number of edges of a graph of maximum degree $r$ and line diameter $D$; $n(2,2,r)\ge\frac54r^2$ for even $r$ by $C_5\otimes S_t$; Kleitman's reported bound $n(2,2,r)\le\frac54r^2$, so $n(2,2,r)=\frac54r^2$ for even $r$; $\liminf_r n(2,D,r)r^{-D}\ge(\frac12)^{D-1}$, with $v_3,v_4,v_6\ge1$ (Benson, Delorme).

• Moore bound, Section 2: For a graph of maximum degree Delta and diameter at most D, n(Delta,D) <= (Delta(Delta-1)^D - 2)/(Delta-2) for Delta>=3, and n(2,D) <= 2D+1; graphs attaining it are the Moore graphs, which exist only for Delta=2 (odd cycles), D=1 (cliques), or D=2 with Delta=3 (Petersen) or Delta=7 (Hoffman-Singleton), and possibly D=2 with Delta=57 (PDF p. 3 right-hand to p. 4 left-hand page).

• Bipartite Moore bound, Section 2: For even girth g=2D the minimum number of vertices of a Delta-regular graph is n_1(Delta,g) = 2D if Delta=2 and (2(Delta-1)^D - 2)/(Delta-2) if Delta>=3; the extremal graphs are called bipartite Moore graphs.

• Plesník / Chung-Garey diameter vulnerability, Section 5: Deleting an edge from a graph of diameter D leaves it disconnected or of diameter at most 2D (Plesník 1975); removing s edges leaves a graph that, if connected, has diameter at most (s+1)D + O(s) (Chung and Garey 1983), proved via the bound n/(s+1) - 1 <= D' < n/(s+1) + 3 for adding s edges to a path on n vertices.

• Murty-Vijayan extremal functions, Section 5: Survey of f_v(n,D,D',s) and f_e(n,D,D',s), the minimum number of edges of a graph of order n and diameter D whose diameter stays at most D' after deleting any s vertices (resp. edges), including Enomoto-Usami's exact value f_v(n,D,D',1) = ceil((Dn-2D-1)/(D-1)) for n > D' >= 2D-1.

• Diameter-critical graphs conjecture, Section 5: Plesník, Murty and Simon conjectured the bound floor(n^2/4) on the number of edges of an n-vertex diameter-2 graph in which deleting any edge increases the diameter (an edge-critical graph); Caccetta and Häggkvist (1979) obtained the bound (1/12)(1+sqrt 5)n^2 < 0.27n^2.

• Hypergraph Moore bound, Section 6: A (Delta,D,r)-hypergraph (diameter D, maximum degree Delta, maximum edge size r) satisfies n(Delta,D,r) <= 1 + Delta(r-1) sum_{i=0}^{D-1} (Delta-1)^i (r-1)^i, reducing to the classical Moore bound when r=2.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.