login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A064513 Maximal number of nodes in graph of degree <= n and diameter 2 (another version). 1
2, 5, 10, 15, 24, 32, 50 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Comment from Allan C. Wechsler, Nov 22 2015: a(8) <= 65 by the Moore bound. Since 8 is not in {2,3,7,57}, we know a(8) <= 64. I don't know if we have any better upper bounds. This seems like a decent undergraduate research project. Pushing up the lower bound also.

REFERENCES

Hoffman, Alan J.; Singleton, Robert R., Moore graphs with diameter 2 and 3, IBM Journal of Research and Development 5 (1960), 497-504.

Loz, Eyal; Siran Jozef, New record graphs in the degree-diameter problem, Australasian Journal of Combinatorics 41 (1968), 63-80.

McKay, Brendan D.; Miller, Mirka; Siran, Jozef, A note on large graphs of diameter two and given maximum degree, Journal of Combinatorial Theory Series B 74 (1968): 110-118.

Pineda-Villavicencio, Guillermo; Gómez, José; Miller, Mirka; Pérez-Rosésd, Hebert, New Largest Graphs of Diameter 6, Electronic Notes in Discrete Mathematics 24 (2006), 153-160.

LINKS

Table of n, a(n) for n=1..7.

F. Comellas, (Degree,Diameter) Problem for Graphs

J. Dinneen, Michael; Hafner, Paul R., New Results for the Degree/Diameter Problem, Networks 24 (1995), 359-367, arXiv:math/9504214.

Mirka Miller, Jozef Sirán, Moore Graphs and Beyond: A survey of the Degree/Diameter Problem, Electronic Journal of Combinatorics, Dynamic Survey DS14.

Wikipedia, Table of the largest known graphs of a given diameter and maximal degree

Wikipedia, Hoffman-Singleton Graph

EXAMPLE

a(2) = 5 is achieved by the 5-cycle.

a(3) = 10 is achieved by the Petersen graph.

CROSSREFS

Sequence in context: A267454 A163059 A099738 * A117582 A002134 A243971

Adjacent sequences:  A064510 A064511 A064512 * A064514 A064515 A064516

KEYWORD

nonn,nice,hard,more

AUTHOR

N. J. A. Sloane, Oct 07 2001

EXTENSIONS

It is known that a(8) >= 57.

Corrected and extended by N. J. A. Sloane, Nov 17 2015 following suggestions from Allan C. Wechsler and Christopher E. Thompson.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 17 15:19 EDT 2019. Contains 325106 sequences. (Running on oeis4.)