Cayley graphs and the degree-diameter problem

Collection Cayley graphs and the degree-diameter problem

Organisateur(s) Sarfraz Ahmad, Edgar Martínez-Moro
Date(s) 01/11/2022 - 11/11/2022
URL associée https://lahore.comsats.edu.pk/cimpa2022/index.aspx
00:00:00 / 00:00:00
4 5

Cayley graphs and the degree-diameter problem (3/4)

De Tomas Vetrik

The degree-diameter problem is to determine the largest number of vertices in a graph of maximum degree $d$ and diameter $k$. The problem is motivated by network design. The topology of a network (such as telecommunications, multiprocessor, or local area network) is usually modelled by a graph in which vertices represent nodes (stations or processors) while edges stand for links or other types of connections. The network interpretation of the two parameters (diameter of a graph and vertex degrees) is obvious. The degree of a vertex is the number of connections attached to a node, while the diameter indicates the largest number of links that must be traversed in order to transmit a message between any two nodes. It is known that the number of vertices in a graph of maximum degree $d$ and diameter $k$ cannot exceed the Moore bound. Research activities related to the degree-diameter problem fall into two main streams. On one hand there are proofs of non-existence of graphs of order close to the Moore bound, on the other hand there is a great deal of activity in constructions of large graphs of given maximum degree and diameter. I present definitions, introduction and some results in this area in a simple way, so also students will be able to follow the lectures.

Informations sur la vidéo

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis