Produit fort (graphe)

Soient deux graphes ${\displaystyle G}$ et ${\displaystyle H}$. Le produit tensoriel ${\displaystyle G\boxtimes H}$ est défini comme suit[1] :

• l'ensemble de ses sommets est le produit cartésien ${\displaystyle V(G)\times V(H)}$ ;
• ${\displaystyle (g,h)}$ et ${\displaystyle (g',h')}$ sont adjacents dans ${\displaystyle G\boxtimes H}$ si et seulement si l'une de ces conditions est vérifiée :
  • ${\displaystyle g=g'}$ et ${\displaystyle h}$ est adjacent à ${\displaystyle h'}$
  • ${\displaystyle g}$ est adjacent à ${\displaystyle g'}$ et ${\displaystyle h=h'}$
  • ${\displaystyle g}$ est adjacent à ${\displaystyle g'}$ et ${\displaystyle h}$ est adjacent à ${\displaystyle h'}$.

Le produit fort est l'union du produit cartésien et du produit tensoriel.