×

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.)
Software:
nauty
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] 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
[2] 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.
[3] Brown, W.G., On graphs that do not contain a thompsen graph, Canad. math. bull., 9, 281-285, (1966) · Zbl 0178.27302
[4] Cameron, P.J., Automorphism groups of graphs, Selected topics in graph theory 2, (1983), Academic Press New York, p. 87-127
[5] Delorme, C., Large bipartite graphs with given degree and diameter, J. graph theory, 8, 325-334, (1985) · Zbl 0623.05048
[6] Delorme, C., Grands graphes de degré et diamètre donnés, Europ. J. combin., 6, 291-302, (1985)
[7] Delorme, C., Examples of products giving large graphs with given degree and diameter, Discrete appl. math., 37/38, 157-167, (1992) · Zbl 0768.05034
[8] Dineen, M.J.; Hafner, P.R., New results for the degree/diameter problem, Networks, 24, 359-367, (1994) · Zbl 0806.05039
[9] Elspas, B., Topological constraints on interconnection-limited logic, Proc. 5th ann. symp. switching circuit theory and logic design, (1964), p. 133-147
[10] Erdős, P.; Fajtlowicz, S.; Hoffman, A.J., Maximum degree in graphs of diameter 2, Networks, 10, 87-90, (1980) · Zbl 0427.05042
[11] Godsil, C.D., Algebraic combinatorics, (1993), Chapman & Hall London/New York · Zbl 0814.05075
[12] T. S. Griggs, May 1996
[13] Gross, J.L.; Tucker, T.W., Topological graph theory, (1987), Wiley New York · Zbl 0621.05013
[14] Hafner, P.R., Large Cayley graphs and digraphs with small degree and diameter, (), 291-302 · Zbl 0830.05025
[15] 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
[16] Huxley, M.N., On the difference between consecutive primes, Invent. math., 15, 164-170, (1972) · Zbl 0241.10026
[17] 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.