𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On large (Δ, 6)-Graphs

✍ Scribed by J. Gómez Martí

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
100 KB
Volume
46
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

In this article, a new method is proposed for obtaining large-diameter 6 graphs by replacing some vertices of a Moore bipartite diameter 6 graph by complete K h graphs. These complete graphs are joined to the remaining nonmodified graph and to each other by means of new edges. More precisely, these new edges are those of a bipartite diameter 3 graph, together with some appropriate extra edges. The degree and the diameter of the graph so constructed coincide with those of the original one. The construction put forward here gives rise to some of the largest known diameter 6 graphs.

📜 SIMILAR VOLUMES

On large (Δ, D, D, 1)-graphs
On large (Δ, D, D, 1)-graphs
✍ J. Gómez; J. Fàbrega; J.L.A. Yebra 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 352 KB
On graphs with subgraphs having large in
On graphs with subgraphs having large independence numbers
✍ Noga Alon; Benny Sudakov 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

## Abstract Let __G__ be a graph on __n__ vertices in which every induced subgraph on ${s}={\log}^{3}\, {n}$ vertices has an independent set of size at least ${t}={\log}\, {n}$. What is the largest ${q}={q}{(n)}$ so that every such __G__ must contain an independent set of size at least __q__? This