The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices (Q1173631): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0012-365x(90)90161-a / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2024152022 / rank | |||
Normal rank | |||
Latest revision as of 10:07, 30 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices |
scientific article |
Statements
The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices (English)
0 references
25 June 1992
0 references
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.
0 references
maximum number of edges
0 references
simple graph
0 references
extremal graphs
0 references
0 references
