9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

VT graphs of given degree and diameter

Presented by Martin MAčAJ
Type: Oral presentation
Track: Symmetries in Graphs, Maps and Other Discrete Structures

Content

A $(k;D)$-graph is a (finite, simple) $k$-regular graph of diameter $D$. The Degree/Diameter Problem is the problem of determining the order $n(k;D)$ of the largest $(k;D)$-graphs. The well-known Moore bound serves as an upper bound on the order of $(k;D)$-graphs. In terms of $k$ and $D$, it can be stated as follows: $M(k; g) = 1 + k + k(k - 1) + \dots + k(k -1)^{D-1}.$ In our talk we show that for any fixed degree $k\geq 3$ and any positive integer $K$ the largest vertex-transitive $(k;D)$ graph has size at most $M(k;D)-K$ for almost all (in the asymptotic sense) diameters $D$. This is a joint work with G. Exoo R. Jajcay and J \v Sir\'a\v n

Place

Location: Koper, Slovenia

Primary authors

More

Co-authors

More