Concept

Degree diameter problem

In graph theory, the degree diameter problem is the problem of finding the largest possible graph G (in terms of the size of its vertex set V) of diameter k such that the largest degree of any of the vertices in G is at most d. The size of G is bounded above by the Moore bound; for 1 < k and 2 < d only the Petersen graph, the Hoffman-Singleton graph, and possibly one more graph (not yet proven to exist) of diameter k = 2 and degree d = 57 attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound. Let be the maximum possible number of vertices for a graph with degree at most d and diameter k. Then , where is the Moore bound: This bound is attained for very few graphs, thus the study moves to how close there exist graphs to the Moore bound. For asymptotic behaviour note that . Define the parameter . It is conjectured that for all k. It is known that and that .

Official source

https://en.wikipedia.org/wiki/Degree_diameter_problem

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (1)

Ceramic and Colloidal Processing

Covers the analysis and processing of ceramic materials using the Saturn DigiSizer II 5205.

Related publications (2)

Lower bounds for Ramsey numbers of bounded degree hypergraphs

We prove that, for all k≥3, and any integers Δ,n with n≥Δ, there exists a k-uniform hypergraph on n vertices with maximum degree at most Δ whose 4-color Ramsey number is at least twk(ckΔ)⋅n, for some constant ck>0, where twk denotes the tower function. For k≥4, this is tight up to the constant ck and for k=3 it is known to be tight up to a factor of log⁡Δ on top of the tower. Our bound extends a well-known result of Graham, Rödl and Ruciński for graphs and answers a question of Conlon, Fox and Sudakov from

Elsevier2026

Scaling a Reliable Distributed System

We consider the problem of reliably connecting an arbitrarily large set of computers (nodes) with communication channels. Reliability means here the ability, for any two nodes, to remain connected (i.e., their ability to communicate) with probability at least mu, despite the very fact that every other node or channel has an independent probability lambda of failing. A simple solution to the problem consists in connecting every pair of nodes with several channels. This solution however does not scale: the nu

LPD EPFL2016

Related people (1)

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.