A note on large graphs of diameter two and given maximum degree (Q1272472): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: Brendan D. McKay / rank
 
Normal rank
Property / author
 
Property / author: Jozef Širáň / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Ján Plesník / rank
 
Normal rank

Revision as of 03:10, 10 February 2024

scientific article
Language Label Description Also known as
English
A note on large graphs of diameter two and given maximum degree
scientific article

    Statements

    A note on large graphs of diameter two and given maximum degree (English)
    0 references
    0 references
    0 references
    0 references
    23 April 1999
    0 references
    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.
    0 references
    graph
    0 references
    degree
    0 references
    diameter
    0 references
    group
    0 references
    Moore bound
    0 references
    vertex-transitive
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references