|
Graph Product
In graph theory, a graph product is a binary operation on Graph (discrete mathematics), graphs. Specifically, it is an operation that takes two graphs and and produces a graph with the following properties: * The vertex (graph theory), vertex set of is the Cartesian product , where and are the vertex sets of and , respectively. * Two vertices and of are connected by an edge (graph theory), edge, If and only if, iff a condition about in and in is fulfilled. The graph products differ in what exactly this condition is. It is always about whether or not the vertices in are equal or connected by an edge. The terminology and notation for specific graph products in the literature varies quite a lot; even if the following may be considered somewhat standard, readers are advised to check what definition a particular author uses for a graph product, especially in older texts. Overview table The following table shows the most common graph products, with \sim denoting "is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated wi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lexicographical Product Of Graphs
In graph theory, the lexicographic product or (graph) composition of graphs and is a graph such that * the vertex set of is the cartesian product ; and * any two vertices and are adjacent in if and only if either is adjacent with in or and is adjacent with in . If the edge relations of the two graphs are order relations, then the edge relation of their lexicographic product is the corresponding lexicographic order. The lexicographic product was first studied by . As showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem. Properties The lexicographic product is in general noncommutative: . However it satisfies a distributive law with respect to disjoint union: . In addition it satisfies an identity with respect to complementation: . In particular, the lexicographic product of two self-complementary graphs is self-complementary. The independence number of a lexicographic produ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Replacement Product
In graph theory, the replacement product of two graphs is a graph product that can be used to reduce the degree of a graph while maintaining its connectivity. Suppose ''G'' is a ''d''-regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ... and ''H'' is an ''e''-regular graph with vertex set . Let ''R'' denote the replacement product of ''G'' and ''H''. The vertex set of ''R'' is the Cartesian product ''V''(''G'') × ''V''(''H''). For each vertex ''u'' in ''V''(''G'') and for each edge (''i'', ''j'') in ''E''(''H''), the vertex (''u'', ''i'') is adjacent to (''u'', ''j'') in ''R''. Furthermore, for each edge (''u'', ''v'') in ''E''(''G''), if ''v'' is the ''i''th neighbor of ''u'' and ''u'' is the ''j''th neighbor of ''v'', the vertex (''u'',&nb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zig-zag Product
In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, is a binary operation which takes a large graph (G) and a small graph (H) and produces a graph that approximately inherits the size of the large one but the degree of the small one. An important property of the zig-zag product is that if H is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of G. Roughly speaking, the zig-zag product G \circ H replaces each vertex of G with a copy (cloud) of H, and connects the vertices by moving a small step (zig) inside a cloud, followed by a big step (zag) between two clouds, and finally performs another small step inside the destination cloud. The zigzag product was introduced by . When the zig-zag product was first introduced, it was used for the explicit construction of constant degree expanders and extractors. Later on, the zig-zag product was used in computational complexity theory to prove that symmetric ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rooted Product Of Graphs
In mathematical graph theory, the rooted product of a graph ''G'' and a rooted graph ''H'' is defined as follows: take , ''V''(''G''), copies of ''H'', and for every vertex v_i of ''G'', identify v_i with the root node of the ''i''-th copy of ''H''. More formally, assuming that ''V''(''G'') = , ''V''(''H'') = and that the root node of ''H'' is h_1, define :G \circ H := (V, E) where :V = \left\ and :E = \left\ \cup \bigcup_^n \left\ If ''G'' is also rooted at ''g''1, one can view the product itself as rooted, at (''g''1, ''h''1). The rooted product is a subgraph of the cartesian product of the same two graphs. Applications The rooted product is especially relevant for trees, as the rooted product of two trees is another tree. For instance, Koh et al. (1980) used rooted products to find graceful numberings for a wide family of trees. If ''H'' is a two-vertex complete graph ''K''2, then for any graph ''G'', the rooted product of ''G'' and ''H'' has domination number exactly ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modular Product Of Graphs
In graph theory, the modular product of graphs ''G'' and ''H'' is a graph formed by combining ''G'' and ''H'' that has applications to subgraph isomorphism. It is one of several different kinds of graph products that have been studied, generally using the same vertex set (the Cartesian product of the sets of vertices of the two graphs ''G'' and ''H'') but with different rules for determining which edges to include. Definition The vertex set of the modular product of ''G'' and ''H'' is the cartesian product ''V''(''G'') × ''V''(''H''). Any two vertices (''u'', ''v'') and (''u' '', ''v' '') are adjacent in the modular product of ''G'' and ''H'' if and only if ''u'' is distinct from ''u' '', ''v'' is distinct from ''v' '', and either * ''u'' is adjacent with ''u' '' and ''v'' is adjacent with ''v' '', or * ''u'' is not adjacent with ''u' '' and ''v'' is not adjacent with ''v' ''. Application to subgraph isomorphism Cliques in the modular product graph correspo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Strong Product Of Graphs
In 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. An example of a strong product is the king's graph, the graph of moves of a chess king on a chessboard, which can be constructed as a strong product of path graphs. Decompositions of planar graphs and related graph classes into strong products have been used as a central tool to prove many other results about these graphs. Care should be exercised when encountering the term ''strong product'' in the literature, since it has also been used to denote the tenso ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Binary Operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary operation ''on a set'' is a binary operation whose two domains and the codomain are the same set. Examples include the familiar arithmetic operations of addition, subtraction, and multiplication. Other examples are readily found in different areas of mathematics, such as vector addition, matrix multiplication, and conjugation in groups. An operation of arity two that involves several sets is sometimes also called a ''binary operation''. For example, scalar multiplication of vector spaces takes a scalar and a vector to produce a vector, and scalar product takes two vectors to produce a scalar. Such binary operations may be called simply binary functions. Binary operations are the keystone of most algebraic structures that are studie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
