|
Graph Products
In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs and and produces a graph with the following properties: * The 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, 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. Even for more standard definitions, it is not always consistent in the literature how to handle self-loops. The formulas below for the number of edges in a product also may fail when inc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') which are connected by ''Glossary of graph theory terms#edge, edges'' (also called ''arcs'', ''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 (mathematics), set of vertices (also called nodes or points); * ... [...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 to in or and is adjacent to 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 product m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Corona Product
In graph theory, the corona product of graphs and , denoted G \circ H, can be obtained by taking one copy of , called the center graph, and a number of copies of equal to the order of . Then, each copy of is assigned a vertex in , and that one vertex is attached to each vertex in its corresponding copy by an edge. The star edge coloring of a graph is a proper edge coloring without bichromatic paths and cycles of length four, similar to the star coloring of a graph, but coloring the edges instead of the vertices. The star edge chromatic index \chi'_(G) of the corona product of a path graph with cycle, wheel, helm and gear graphs are known. See also *Graph operations In the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations. Unary operations Unary operations create a new gra ... * Graph product References External links * * {{graph-stu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Replacement Product
In graph theory, the replacement product of two Graph (discrete mathematics), graphs is a graph product that can be used to reduce the degree (graph theory), degree of a graph while maintaining its connectivity (graph theory), connectivity. Suppose is a -regular graph and is an -regular graph with vertex set Let denote the replacement product of and . The vertex set of is the Cartesian product . For each vertex in and for each edge in , the vertex is adjacent to in . Furthermore, for each edge in , if is the th neighbor of and is the th neighbor of , the vertex is adjacent to in . If is an -regular graph, then is an -regular graph. References External links * Graph products {{Graph-stub ... [...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 Graph operations, 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 (graph theory), degree of the small one. An important property of the zig-zag product is that if H is a good Expander graph, 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. More specifically, the start and endpoints for each edge are at the beginning and end of this "zig-zag-zig" process starting at the points in the replacement product of the two graphs. The zigzag product was introd ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rooted Product Of Graphs
In mathematical graph theory, the rooted product of a graph and a rooted graph is defined as follows: take copies of , and for every vertex of , identify with the root node of the -th copy of . More formally, assuming that :\begin V(G) &= \, \\ V(H) &= \, \end and that the root node of is , define :G \circ H := (V, E), where :V = \left\ and :E = \Bigl\ \cup \bigcup_^n \Bigl\. If is also rooted at , one can view the product itself as rooted, at . 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 is a two-vertex complete graph , then for any graph , the rooted product of and has domination number exactly half of its number of vertices. Every connected graph in which the domination number is half the numb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modular Product Of Graphs
In graph theory, the modular product of graphs and is a graph formed by combining and 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 and ) but with different rules for determining which edges to include. Definition The vertex set of the modular product of and is the cartesian product . Any two vertices and are adjacent in the modular product of and if and only if is distinct from , is distinct from , and either * is adjacent with and is adjacent with , or * is not adjacent with and is not adjacent with . Application to subgraph isomorphism Cliques in the modular product graph correspond to isomorphisms of induced subgraphs of and . Therefore, the modular product graph can be used to reduce problems of induced subgraph isomorphism to problems of finding cliques in graphs. Specific ... [...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 te ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
