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