Corona Product
   HOME



picture info

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]  


picture info

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]  


picture info

Order (graph Theory)
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a Set (mathematics), set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' means that ''A'' owes money to ''B'', then this graph is directed, because owing mon ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Star Coloring
In the mathematical field of graph theory, a star coloring of a graph is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by . The star chromatic number of is the fewest colors needed to star color . One generalization of star coloring is the closely related concept of acyclic coloring, where it is required that every cycle uses at least three colors, so the two-color induced subgraphs are forests. If we denote the acyclic chromatic number of a graph by , we have that , and in fact every star coloring of is an acyclic coloring. The star chromatic number has been proved to be bounded on every proper minor closed class by . This results was further generalized by to all low-tree-depth colorings (standard coloring and star coloring being low-tree-de ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


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 graph from a single initial graph. Elementary operations Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc. The graph edit distance between a pair of graphs is the minimum number of elementary operations required to transform one graph into the other. Advanced operations Advanced operations create a new graph from an initial one by a complex change, such as: * transpose graph; * complement graph; * line graph; * graph minor; * graph rewriting; * power of graph; * dual graph; * medial graph; * quotient graph; * Y- ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Graph Product
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 in ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]