𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The maximum number of edges in 2K2-free graphs of bounded degree

✍ Scribed by F.R.K. Chung; A. Gyárfás; Z. Tuza; W.T. Trotter

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
481 KB
Volume
81
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Maximum number of colorings of (2k, k2)-
Maximum number of colorings of (2k, k2)-graphs
✍ Felix Lazebnik; Oleg Pikhurko; Andrew Woldar 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract Let ${\cal F}\_{{2}{k},{k}^{2}}$ consist of all simple graphs on 2__k__ vertices and ${k}^{2}$ edges. For a simple graph __G__ and a positive integer $\lambda$, let ${P}\_{G}(\lambda)$ denote the number of proper vertex colorings of __G__ in at most $\lambda$ colors, and let $f(2k, k^{2

The maximum number of edges in a minimal
The maximum number of edges in a minimal graph of diameter 2
✍ Zoltán Füredi 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 717 KB

## 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

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