𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Brendan D McKay; Mirka Miller; Jozef Širáň

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
242 KB
Volume
74
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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+2)Â2X. Using voltage graphs, we construct a family of vertex-transitive non-Cayley graphs which shows that vt(d, 2) (8Â9)(d+ 1 2 ) 2 for all d of the form d=(3q&1)Â2, where q is a prime power congruent with 1 (mod 4). The construction generalizes to all prime powers and yields large highly symmetric graphs for other degrees as well. In particular, for d=7 we obtain as a special case the Hoffman Singleton graph, and for d=11 and d=13 we have new largest graphs of diameter 2, and degree d on 98 and 162 vertices, respectively.

📜 SIMILAR VOLUMES

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

Extremal graphs of diameter two and give
Extremal graphs of diameter two and given maximum degree, embeddable in a fixed surface
✍ Knor, Martin; ?ir�?, Jozef 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

It is known that for each d there exists a graph of diameter two and maximum degree d which has at least (d/2) (d + 2)/2 vertices. In contrast with this, we prove that for every surface S there is a constant d S such that each graph of diameter two and maximum degree d ≥ d S , which is embeddable in

Large Cayley graphs and vertex-transitiv
Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
✍ Heather Macbeth; Jana Šiagiová; Jozef Širáň; Tomáš Vetrík 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract For any __d__⩾5 and __k__⩾3 we construct a family of Cayley graphs of degree __d__, diameter __k__, and order at least __k__((__d__−3)/3)^__k__^. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide ra

On the largest tree of given maximum deg
On the largest tree of given maximum degree in a connected graph
✍ Y. Caro; I. Krasikov; Y. Roditty 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 1 views

## Abstract We prove that every connected graph __G__ contains a tree __T__ of maximum degree at most __k__ that either spans __G__ or has order at least __k__δ(__G__) + 1, where δ(__G__) is the minimum degree of __G.__ This generalizes and unifies earlier results of Bermond [1] and Win [7]. We als

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 3 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.