The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices (Q1173631): Difference between revisions

Let \(f(n,k)\) denote the maximum number of edges in a simple graph on \(n\) vertices with at most \(k\) edge-disjoint paths connecting any two adjacent vertices. \textit{W. Mader} [Math. Ann. 194, 295--312 (1971; Zbl 0213.50801)] showed that \(f(n,k)\leq k(n-k)\) for \(6\leq 3k\leq n\). The author shows that \(f(n,k)=\lfloor(n+k)^ 2/8\rfloor\) for \(k+1\leq n\leq 3k-1\), and determines the extremal graphs.