The maximum number of edges in a graph with fixed edge-degree (Q1382818)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1130767
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The maximum number of edges in a graph with fixed edge-degree |
scientific article; zbMATH DE number 1130767 |
Statements
The maximum number of edges in a graph with fixed edge-degree (English)
0 references
18 March 1998
0 references
For \(t\geq 17\) and \(n\geq 2t+2\), let \(G\) be a graph with \(n\) vertices whose complement is connected, and such that for all non-adjacent vertices \(u,v\), there are at least \(t\) common neighbours. It is proved that \(| E(G)|\geq \lceil((2t+1)n- 2t^2- 3)/2\rceil\) for \(n\leq 3t-1\), and \(| E(G)|\geq (t+1)n- t^2- t-3\) for \(n\geq 3t\). Furthermore, it is shown that both of these results are sharp.
0 references
maximum number of edges
0 references
fixed edge-degree
0 references
