✦ LIBER ✦

A family of graphs and the degree/diameter problem

✍ Scribed by Geoffrey Exoo

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 64 KB
Volume: 37
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1007

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We investigate a family of graphs relevant to the problem of finding large regular graphs with specified degree and diameter. Our family contains the largest known graphs for degree/diameter pairs (3, 7), (3, 8), (4, 4), (5, 3), (5, 5), (6, 3), (6, 4), (7, 3), (14, 3), and (16, 2). We also find a new bound for (3, 6) by an unrelated method. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 118–124, 2001

📜 SIMILAR VOLUMES

Decreasing the diameter of bounded degre

Decreasing the diameter of bounded degree graphs

✍ Noga Alon; András Gyárfás; Miklós Ruszinkó 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 2 views

Maximum degree in graphs of diameter 2

✍ Paul Erdös; Siemion Fajtlowicz; Alan J. Hoffman 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

New results for the degree/diameter prob

New results for the degree/diameter problem

✍ Michael J. Dinneen; Paul R. Hafner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 489 KB

The minimum order of a cayley graph with

The minimum order of a cayley graph with given degree and diameter

✍ Yahya Ould Hamidoune 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

Some large graphs with given degree and

Some large graphs with given degree and diameter

✍ I. Alegre; M. A. Fiol; J. L. A. Yebra 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 196 KB 👁 1 views

This paper considers the (A, 0 ) problem: to maximize the order of graphs with given maximum degree A and diameter 0, of importance for its implications in the design of interconnection networks. Two cubic graphs of diameters 5 and 8 and orders 70 and 286, respectively, and a graph of degree 5, diam

A Note on Large Graphs of Diameter Two a

A Note on Large Graphs of Diameter Two and Given Maximum Degree

✍ Brendan D McKay; Mirka Miller; Jozef Širáň 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Let vt(d, 2) be the largest order of a vertex-transitive graph of degree d and diameter 2. It is known that vt(d, 2)=d 2 +1 for d=1, 2, 3, and 7; for the remaining values of d we have vt(d, 2) d 2 &1. The only known general lower bound on vt(d, 2), valid for all d, seems to be vt(d, 2) w(d+2)Â2x W(d