In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the degree diameter problem is the problem of finding the largest possible graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 G (in terms of the size of its vertex

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 set V) of diameter

Distance (graph theory)

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance...

 k such that the largest degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum 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

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

, the Hoffman-Singleton graph

Hoffman-Singleton graph

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters . It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is...

 and maybe a graph 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.

See also

• Cage (graph theory)
  Cage (graph theory)
  In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an -graph exists...
  
  
• Table of degree diameter graphs
  Table of graphs
  In graph theory, the degree diameter problem is the problem of finding the largest possible graph for a given maximum degree and diameter. The Moore bound sets limits on this, but for many years mathematicians in the field have been interested in a more precise answer...
  
  
• Table of vertex-symmetric degree diameter digraphs
  Table of vertex-symmetric digraphs
  -Table of the orders of the largest known vertex-symmetric graphs for the directed degree diameter problem:Below is the table of the best known vertex transitive digraphs in the directed Degree diameter problem....
  
  
• Maximum degree-and-diameter-bounded subgraph problem
  MaxDDBS
  The maximum degree-and-diameter-bounded subgraph problem is a problem in graph theory.Given a connected host graph G, an upper bound for the degree d, and an upper bound for the diameter k, we look for the largest subgraph S of G with maximum degree at most d and diameter at most k...