𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum degree in graphs of diameter 2

✍ Scribed by Paul Erdös; Siemion Fajtlowicz; Alan J. Hoffman

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
163 KB
Volume
10
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

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

Maximum pebbling number of graphs of dia
Maximum pebbling number of graphs of diameter three
✍ Boris Bukh 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 1 views

## Abstract Given a configuration of pebbles on the vertices of a graph __G__, a __pebbling move__ consists of taking two pebbles off some vertex __v__ and putting one of them back on a vertex adjacent to __v__. A graph is called __pebbleable__ if for each vertex __v__ there is a sequence of pebbli

Improper choosability of graphs and maxi
Improper choosability of graphs and maximum average degree
✍ Frédéric Havet; Jean-Sébastien Sereni 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract Improper choosability of planar graphs has been widely studied. In particular, Škrekovski investigated the smallest integer __g__~k~ such that every planar graph of girth at least __g__~k~ is __k__‐improper 2‐choosable. He proved [9] that 6 ≤ __g__~1~ ≤ 9; 5 ≤  __g__~2~ ≤ 7; 5 ≤ __g__~3

A family of graphs and the degree/diamet
A family of graphs and the degree/diameter problem
✍ Geoffrey Exoo 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 1 views

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