login
The OEIS is supported by the many generous donors 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

%I #36 Feb 27 2020 11:47:19

%S 2,5,10,15,24,32,50

%N Maximal number of nodes in graph of degree <= n and diameter 2 (another version).

%C 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.

%H F. Comellas, <a href="http://maite71.upc.es/grup_de_grafs/grafs/taula_delta_d.html">(Degree,Diameter) Problem for Graphs</a>

%H J. Dinneen, Michael; Hafner, Paul R., <a href="http://arxiv.org/abs/math/9504214">New Results for the Degree/Diameter Problem</a>, Networks 24 (1995), 359-367, arXiv:math/9504214 [math.CO], 1995.

%H Alan J. Hoffman, Robert R. Singleton, <a href="https://doi.org/10.1147/rd.45.0497">Moore graphs with diameter 2 and 3</a>, IBM Journal of Research and Development 5 (1960), 497-504.

%H Eyal Loz, Jozef Siran, <a href="https://ajc.maths.uq.edu.au/pdf/41/ajc_v41_p063.pdf">New record graphs in the degree-diameter problem</a>, Australasian Journal of Combinatorics 41 (1968), 63-80.

%H Brendan McKaya, Mirka Miller, Jozef Širáň, <a href="https://doi.org/10.1006/jctb.1998.1828">A note on large graphs of diameter two and given maximum degree</a>, Journal of Combinatorial Theory Series B 74 (1968): 110-118.

%H Mirka Miller, Jozef Sirán, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS14">Moore Graphs and Beyond: A survey of the Degree/Diameter Problem</a>, Electronic Journal of Combinatorics, Dynamic Survey DS14.

%H Guillermo Pineda-Villavicencio; José Gómez; Mirka Miller, Hebert Pérez-Rosés, <a href="https://doi.org/10.1016/j.endm.2006.06.044">New Largest Graphs of Diameter 6</a>, Electronic Notes in Discrete Mathematics 24 (2006), 153-160.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree">Table of the largest known graphs of a given diameter and maximal degree</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph">Hoffman-Singleton Graph</a>

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

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

%K nonn,nice,hard,more

%O 1,1

%A _N. J. A. Sloane_, Oct 07 2001

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

%E Corrected and extended by _N. J. A. Sloane_, Nov 17 2015 following suggestions from _Allan C. Wechsler_ and _Christopher E. Thompson_.

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 04:13 EDT 2024. Contains 371235 sequences. (Running on oeis4.)