Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 25.10.2006 at 10:40 in S5, there is the following noon lecture:

On the Degree/Diameter Problem for both bipartite and non-bipartite graphs

Guillermo Pineda Villavicencio

University of Oriente, Santiago, Cuba

Abstract

Degree/Diameter Problem: Given natural numbers Delta and D, to find the largest possible number of vertices (nB_{Delta,D}) n_{Delta,D} in a (bipartite) graph of maximum degree Delta and diameter at most D. An upper bound for both nB_{Delta,D} and n_{Delta,D} is given by the following expressions.

nB_{Delta,D} <= 1 + Delta + Delta(Delta-1) +...+ Delta(Delta-1)^{D-2} + (Delta-1)^{D-1}

n_{Delta,D} <= 1 + Delta + Delta(Delta-1) +...+ Delta(Delta-1)^{D-2} + Delta(Delta-1)^{D-1}

These expressions are known as the Bipartite Moore bound and as the Moore bound, and are denoted by (B(Delta,D)) M(Delta,D), respectively. We survey some old and new results about these problems, with emphasis on graphs of diameter 2, degree Delta and order M(Delta,D)-2. Finally, we give some open problems in this research area.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010