Hamming graph

Hamming graph

Hamming graphs are a special class of graphs used in several branches of mathematics and computer science. Let "S" be a set of "q" elements and "d" a positive integer. The Hamming graph "H"("d","q") has vertex set "Sd", the set of ordered "d"-tuples of elements of "S", or sequences of length "d" from "S". Two vertices are adjacent if they differ in precisely one coordinate.

The special case in which "q" = 2 is also known as the hypercube graph, denoted "Qd". The special cases in which "d" = 1 and "d" = 2 are the complete graph and rook's graph, respectively.

The Hamming graphs are interesting in connection with error-correcting codes and association schemes, to name two areas.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Hamming distance — 3 bit binary cube for finding Hamming distance …   Wikipedia

  • Rook's graph — infobox graph name = Rook s graph image caption = 8x8 Rook s graph vertices = nm edges = nm ( n + m )/2 nm diameter = 2 chromatic number = max( n , m ) chromatic index = girth = 3 (if max( n , m ) ≥ 3) properties = regular, vertex transitive,… …   Wikipedia

  • Graphe de Hamming — H(4,2) Notation H(d,q) Nombre de sommets qd Nombre d arêtes …   Wikipédia en Français

  • Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… …   Wikipedia

  • Hypercube graph — The hypercube graph Q4 Vertices 2n Edges 2n−1n …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Cube — This article is about the geometric shape. For other uses, see Cube (disambiguation). Regular Hexahedron (Click here for rotating model) Type Platonic solid Elements F = 6, E = 12 V = 8 (χ = 2) …   Wikipedia

  • Window function — For the term used in SQL statements, see Window function (SQL) In signal processing, a window function (also known as an apodization function or tapering function[1]) is a mathematical function that is zero valued outside of some chosen interval …   Wikipedia

  • Isoperimetric inequality — The isoperimetric inequality is a geometric inequality involving the square of the circumference of a closed curve in the plane and the area of a plane region it encloses, as well as its various generalizations. Isoperimetric literally means… …   Wikipedia

  • Hypercube (Graphe) — Pour les articles homonymes, voir Hypercube (homonymie).   Cette page se comprend mieux après la lecture de Théorie des graphes. Hypercube …   Wikipédia en Français

Share the article and excerpts

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