Graph Strong Product

Author

Eric W. Weisstein
September 28, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/GraphStrongProduct.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/GraphStrongProduct.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Implementation

GraphProduct

bug(428427): Consider supporting GraphProduct[G, H, "Strong"] as a synonym for GraphProduct[G, H, "Normal"]

GraphProduct[PathGraph[{1,2}],PathGraph[{1,2,3}],"Strong"]

GraphProduct[PathGraph[{1,2}],PathGraph[{1,2,3}],"Normal"]

Adjacency matrices

Hammack et al. (2016)

With[{G=PathGraph[{1,2}],H=PathGraph[{1,2,3}]},
IsomorphicGraphQ[
GraphProduct[G,H,"Normal"],
AdjacencyGraph[KroneckerProduct[AdjacencyMatrix[G],IdentityMatrix[VertexCount[H]]]+KroneckerProduct[IdentityMatrix[VertexCount[G]],AdjacencyMatrix[H]]+KroneckerProduct[AdjacencyMatrix[G],AdjacencyMatrix[H]]]]
]

Combinatorica

<<Combinatorica`

?GraphStrongProduct

GraphStrongProduct[PathGraph[{1,2}],PathGraph[{1,2,3}]]

System`Graph[Edges[GraphStrongProduct[Path[2],Path[3]]]]

ToEntity[%]

System`Graph[Edges[GraphStrongProduct[Path[3],Path[2]]]]

ToEntity[%]

GraphData[{"King",{2,3}},"Graph","All"]

System`Graph[Edges[GraphStrongProduct[Cycle[5],Cycle[5]]]]

ToEntity[%]