The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices (Q1173631): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q5520565 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3852212 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Minimally k-connected graphs of low order and maximal size / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Existenz gewisser Konfigurationen in \(n\)-gesättigten Graphen und in Graphen genügend großer Kantendichte / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4189309 / rank | |||
Normal rank | |||
Revision as of 08:41, 15 May 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
