# zbMATH — the first resource for mathematics

A note on large graphs of diameter two and given maximum degree. (English) Zbl 0911.05031
The well-known degree/diameter problem asks for determining the largest number of vertices in a graph of maximum degree $$d$$ and diameter $$k$$. In this paper the case of vertex-transitive graphs and $$k=2$$ is considered. The upper (Moore) bound is $$d^2+1$$, but the previously known lower bound was asymptotically only $$d^2/4$$. Using voltage graphs, the authors construct vertex-transitive non-Cayley graphs with asymptotically $$8d^2/9$$ vertices for a selected sequence of $$d$$’s.

##### MSC:
 05C12 Distance in graphs 05C35 Extremal problems in graph theory 05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
##### Keywords:
graph; degree; diameter; group; Moore bound; vertex-transitive
nauty
Full Text:
##### References:
  Bermond, J.C.; Delorme, C.; Farhi, G., Large graphs with given degree and diameter II, J. combin. theory ser. B, 36, 32-48, (1984) · Zbl 0539.05038  L. Branković, M. Miller, J. Plesnı́k, J. Ryan, J. Širáň, Large graphs with small diameter and degree: A voltage assignment approach, Australas. J. Combin.  Brown, W.G., On graphs that do not contain a thompsen graph, Canad. math. bull., 9, 281-285, (1966) · Zbl 0178.27302  Cameron, P.J., Automorphism groups of graphs, Selected topics in graph theory 2, (1983), Academic Press New York, p. 87-127  Delorme, C., Large bipartite graphs with given degree and diameter, J. graph theory, 8, 325-334, (1985) · Zbl 0623.05048  Delorme, C., Grands graphes de degré et diamètre donnés, Europ. J. combin., 6, 291-302, (1985)  Delorme, C., Examples of products giving large graphs with given degree and diameter, Discrete appl. math., 37/38, 157-167, (1992) · Zbl 0768.05034  Dineen, M.J.; Hafner, P.R., New results for the degree/diameter problem, Networks, 24, 359-367, (1994) · Zbl 0806.05039  Elspas, B., Topological constraints on interconnection-limited logic, Proc. 5th ann. symp. switching circuit theory and logic design, (1964), p. 133-147  Erdős, P.; Fajtlowicz, S.; Hoffman, A.J., Maximum degree in graphs of diameter 2, Networks, 10, 87-90, (1980) · Zbl 0427.05042  Godsil, C.D., Algebraic combinatorics, (1993), Chapman & Hall London/New York · Zbl 0814.05075  T. S. Griggs, May 1996  Gross, J.L.; Tucker, T.W., Topological graph theory, (1987), Wiley New York · Zbl 0621.05013  Hafner, P.R., Large Cayley graphs and digraphs with small degree and diameter, (), 291-302 · Zbl 0830.05025  Hoffman, A.J.; Singleton, R.R., On Moore graphs with diameters 2 and 3, IBM J. res. develop., 4, 497-504, (1960) · Zbl 0096.38102  Huxley, M.N., On the difference between consecutive primes, Invent. math., 15, 164-170, (1972) · Zbl 0241.10026  McKay, B.D., Technical report, (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.