𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The maximum number of edges in a minimal graph of diameter 2

✍ Scribed by Zoltán Füredi

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
717 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph g of diameter 2 is minimal if the deletion of any edge increases its diameter. Here the following conjecture of Murty and Simon is proved for n < n~o~. If g has n vertices then it has at most n^2^/4 edges. The only extremum is the complete bipartite graph.

📜 SIMILAR VOLUMES

The number of edges in a maximum cycle—d
The number of edges in a maximum cycle—distributed graph
✍ Yongbing Shi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 288 KB

Shi, Y., The number of edges in a maximum cycle-distributed graph, Discrete Mathematics 104 (1992) 205-209. Let f(n) (f\*(n)) be the maximum possible number of edges in a graph (2-connected simple graph) on n vertices in which no two cycles prove that, for every integer n > 3, f(n) 3 n + k + [i( [~(

Maximum degree in graphs of diameter 2
Maximum degree in graphs of diameter 2
✍ Paul Erdös; Siemion Fajtlowicz; Alan J. Hoffman 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB
The maximum number of edges in 2K2-free
The maximum number of edges in 2K2-free graphs of bounded degree
✍ F.R.K. Chung; A. Gyárfás; Z. Tuza; W.T. Trotter 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 481 KB

A graph is 2K,-free if it does not contain an independent pair of edges as an induced subgraph. We show that if G is 2K,-free and has maximum degree A(G) = D, then G has at most 5D2/4 edges if D is even. If D is odd, this bound can be improved to (5D\* -20 + 1)/4. The extremal graphs are unique.