Strong Graph product between two C_5 graphs?

Questions
, ,
1

Dear Community, I am trying to compute a Strong Graph product between two C_5 graphs. Looking around I did not find anything in the documentation. Only on Internet I found this Mathematica function

GraphComputation`GraphProduct[G, H, type]

at this link:

But I was not able to find any documentation about. Moreover I tried to do something but it seem that only the Cartesian product works:

GraphComputation`GraphProduct[G, H, "Cartesian"]

The other products gives error even if contained in this link:

for example. Thus does someone know how to make Graph Products with Mathematica? Thanks for the attention.

2

You could always implement your own, based on the definition of a strong graph product.

strongGraphProduct[g_, h_] :=
	Block[{mg, mh, vj, n, mj},
		mg = AdjacencyMatrix[g];
		mh = AdjacencyMatrix[h];
		
		vj = Tuples[{Range[VertexCount[g]], Range[VertexCount[h]]}];
		n = Length[vj];
		
		mj = SparseArray[{{i_, j_} /; strongCondition[vj, mg, mh, i, j] -> 1}, {n, n}];
		
		AdjacencyGraph[mj]
	]

strongCondition[vj_, mg_, mh_, i_, j_] :=
	Block[{u1, u2, v1, v2},
		{u1, u2} = vj[[i]];
		{v1, v2} = vj[[j]];
		
		Or[
			u1 === v1 && (mh[[u2, v2]] != 0 || mh[[v2, u2]] != 0),
			u2 === v2 && (mg[[u1, v1]] != 0 || mg[[v1, u1]] != 0),
			(mg[[u1, v1]] != 0 || mg[[v1, u1]] != 0) && (mh[[u2, v2]] != 0 || mh[[v2, u2]] != 0)
		]
	]

Then test it:

g = h = CycleGraph[5];
j = strongGraphProduct[g, h]

7954Screenshot2016-09-0610.44.02.jpg
7954Screenshot2016-09-0610.44.02.jpg352×352 61.8 KB

Some properties:

{VertexCount[j], EdgeCount[j]}
(* {25, 100} *)
3

Thanks for the answer Chip! Of course I created my own function for calculate the Strong Product, even if my code is a bit different from yours. But they are equivalent I guess. I was just surprised that exist a sort of reference about a build-in function that does not exist really.
Thank you again!
Anyway that is my function to get the Strong Product

GraphStrongProduct[G_, H_] :=
 
 Module[{ajmG, ajmH, ajm1G, ajm1H, P, ajmGH} ,
  			(* give the adjacency matrix of the graphs*)
  			
  ajmG = Normal[ArrayFlatten[AdjacencyMatrix[G]]];
  		         ajmH = Normal[ArrayFlatten[AdjacencyMatrix[H ]]];
  			(* give the modified adjacency matrix of the graphs, 
  1 on the diagonal*)
  			ajm1G = ReplacePart[ajmG, {i_, i_} -> 1];
  			ajm1H = ReplacePart[ajmH, {i_, i_} -> 1];
  			(*the adjacent matrix of the strong product between G and H*)
  	\
		P = ArrayFlatten[TensorProduct[ajm1G, ajm1H]];
  			ajmGH = ReplacePart[P, {i_, i_} -> 0];
  			AdjacencyGraph[ajmGH]
  ]

It seems work too.

4

This is a nice solution!

5

You can get around 1.5 times faster if you avoid the pattern matcher by replacing the lines containing ReplacePart with the following:

Change

ajm1G = ReplacePart[ajmG, {i_, i_} -> 1];
ajm1H = ReplacePart[ajmH, {i_, i_} -> 1];

to

ajm1G = Unitize[ajmG + IdentityMatrix[Length[ajmG]]];
ajm1H = Unitize[ajmH + IdentityMatrix[Length[ajmH]]];

and

ajmGH = ReplacePart[P, {i_, i_} -> 0];

to

ajmGH = P (1 - IdentityMatrix[Length[P]]);