TOPICS
Search

Graph Product


In general, a graph product of two graphs G and H is a new graph whose vertex set is V(G)×V(H) and where, for any two vertices (g,h) and (g^',h^') in the product, the adjacency of those two vertices is determined entirely by the adjacency (or equality, or non-adjacency) of g and g^', and that of h and h^'. There are 3×3-1=8 cases to be decided (three possibilities for each, with the case where both are equal eliminated) and thus there are 2^8=256 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); see also Hammack et al. (2016).

Graph products can be computed in the Wolfram Language using GraphProduct[G, H, type].

graph product namesymboldefinition
graph Cartesian productG square H(g=g^' and hadjh^') or (gadjg^' and h=h^')
graph lexicographic productG-H(gadjg^') or (g=g^' and hadjh^')
graph strong productG□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H(g=g^' and hadjh^') or (gadjg^' and h=h^') or (gadjg^' and hadjh^')
graph tensor productG×H(gadjg^' and hadjh^')

See also

Graph Cartesian Product, Graph Tensor Product, Graph Composition, Graph Corona Product, Graph Lexicographic Product, Graph Power, Graph Strong Product, Graph Sum

Portions of this entry contributed by Nicolas Bray

Explore with Wolfram|Alpha

References

Hammack, R.; Imrich, W.; and Klavžar, S. Handbook of Product Graphs, 2nd ed. Boca Raton, FL: CRC Press, 2016.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. and Klavžar, S. Product Graphs: Structure and Recognition. New York: Wiley, 2000.Imrich, W.; KlavĽorezar, 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.

Referenced on Wolfram|Alpha

Graph Product

Cite this as:

Bray, Nicolas and Weisstein, Eric W. "Graph Product." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphProduct.html

Subject classifications