Degree diameter problem

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 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

References

  • Bannai, E.; Ito, T. (1973), "On Moore graphs", J. Fac. Sci. Univ. Tokyo Ser. A 20: 191–208, MR0323615 

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Table of graphs — Table of the orders of the largest known graphs for the undirected Degree Diameter problem= Below is the table of the best known graphs (as of October 2008) in the undirected Degree diameter problem. The following table is the key to the colors… …   Wikipedia

  • 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 (as of October 2008) in the directed Degree diameter problem. The following …   Wikipedia

  • Moore graph — Unsolved problems in mathematics Does a Moore graph with girth 5 and degree 57 exist? In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound An equivalent definition of a Moore …   Wikipedia

  • MaxDDBS — The maximum degree and diameter bounded subgraph problem (MaxDDBS) 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… …   Wikipedia

  • Distributed hash table — A distributed hash table (DHT) is a class of a decentralized distributed system that provides a lookup service similar to a hash table; (key, value) pairs are stored in a DHT, and any participating node can efficiently retrieve the value… …   Wikipedia

  • Distance (graph theory) — Geodesic distance redirects here. For distances on the surface of the Earth, see Great circle distance. 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… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Schmidt-Väisälä camera — The Schmidt Väisälä camera is an astronomical telescopeIntended for wide field (5 to 10 degrees of arc) photographic work. It was designed by Yrjö Väisälä.Invention and designProf. Yrjö Väisälä originally designed an astronomical camera similar… …   Wikipedia

  • Small-world network — In mathematics and physics, a small world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps. A small world network,… …   Wikipedia

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”