Graph labelingIn the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph G = (V, E), a vertex labelling is a function of V to a set of labels; a graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labelling is a function of E to a set of labels. In this case, the graph is called an edge-labeled graph. When the edge labels are members of an ordered set (e.
Tensor product of graphsIn graph theory, the tensor product G × H of graphs G and H is a graph such that the vertex set of G × H is the Cartesian product V(G) × V(H); and vertices (g,h) and math|(''g,h' ) are adjacent in G × H if and only if g is adjacent to g' in G, and h is adjacent to h' in H. The tensor product is also called the direct product, Kronecker product, categorical product, cardinal product, relational product, weak direct product, or conjunction'''.
Unit distance graphIn mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs.
Lattice graphIn graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space \mathbb{R}^n, forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice in the group-theoretical sense. Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a lattice, mesh, or grid.
Crown graphIn graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u_1, u_2, ..., u_n} and {v_1, v_2, ..., v_n} and with an edge from u_i to v_j whenever i ≠ j. The crown graph can be viewed as a complete bipartite graph from which the edges of a perfect matching have been removed, as the bipartite double cover of a complete graph, as the tensor product K_n × K_2, as the complement of the Cartesian direct product of K_n and K_2, or as a bipartite Kneser graph H_n,1 representing the 1-item and (n – 1)-item subsets of an n-item set, with an edge between two subsets whenever one is contained in the other.
Hypercube graphIn graph theory, the hypercube graph Q_n is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^n – 1n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n may also be constructed by creating a vertex for each subset of an n-element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n-digit binary number, with two vertices adjacent when their binary representations differ in a single digit.
Strong product of graphsIn graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.
Median graphIn graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c. The concept of median graphs has long been studied, for instance by or (more explicitly) by , but the first paper to call them "median graphs" appears to be . As Chung, Graham, and Saks write, "median graphs arise naturally in the study of ordered sets and discrete distributive lattices, and have an extensive literature".
Hamming graphHamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) 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 S^d, 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; that is, if their Hamming distance is one. The Hamming graph H(d,q) is, equivalently, the Cartesian product of d complete graphs K_q.
Cayley graphIn mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs.
