Graph Product
المؤلف:
Harary, F.
المصدر:
Graph Theory. Reading, MA: Addison-Wesley, 1994.
الجزء والصفحة:
...
13-4-2022
2636
Graph Product
In general, a graph product of two graphs 
and 
is a new graph whose vertex set is 
and where, for any two vertices 
and 
in the product, the adjacency of those two vertices is determined entirely by the adjacency (or equality, or non-adjacency) of 
and 
, and that of 
and 
. There are 
cases to be decided (three possibilities for each, with the case where both are equal eliminated) and thus there are 
different types of graph products that can be defined.
The most commonly used graph products, given by conditions sufficient and necessary for adjacency, are summarized in the following table (Hartnell and Rall 1998). Note that the terminology is not quite standardized, so these products may actually be referred to by different names by different sources (for example, the graph lexicographic product is also known as the graph composition; Harary 1994, p. 21). Many other graph products can be found in Jensen and Toft (1994).
Graph products can be computed using the unsupported and undocumented Wolfram Language function GraphComputation`GraphProduct[G, H, type].
| graph product name |
symbol |
definition |
| graph Cartesian product |
 |
( and  ) or ( and  ) |
| graph categorical product |
 |
( and  ) |
| graph lexicographic product |
 |
( ) or ( and  ) |
| graph strong product |
![G□AdjustmentBox[x, BoxMargins -> <span style=]() {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H" src="https://mathworld.wolfram.com/images/equations/GraphProduct/Inline24.svg" style="height:22px; width:52px" /> |
( and  ) or ( and  ) or ( and  ) |
REFERENCES
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
Hartnell, B. and Rall, D. "Domination in Cartesian Products: Vizing's Conjecture." In Domination in Graphs--Advanced Topics (Ed. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater). New York: Dekker, pp. 163-189, 1998.
Imrich, W.; Klavzar, S.; and Rall, D. F. Graphs and their Cartesian Product. Wellesley, MA: A K Peters, 2008.Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1994.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
