Tensor product of graphs

<h2 id="examples">Examples</h2>
<ul><li>The tensor product G × K2 is a <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a>, called the <a href="/facts/Bipartite_double_cover/YfyTubqc">bipartite double cover</a> of G. The bipartite double cover of the <a href="/facts/Petersen_graph/lLRxXpQs">Petersen graph</a> is the <a href="/facts/Desargues_graph/M6sXWfFK">Desargues graph</a>: K2 × G(5,2) = G(10,3). The bipartite double cover of a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> Kn is a <a href="/facts/Crown_graph/aauWDwaX">crown graph</a> (a <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> Kn,n minus a <a href="/facts/Perfect_matching/LmtRYLgK">perfect matching</a>).</li>
<li>The tensor product of a complete graph with itself is the <a href="/facts/Complement_(graph_theory)/IdHUPFr3">complement</a> of a <a href="/facts/Rook%2527s_graph/EqVx5BPA">Rook's graph</a>. Its vertices can be placed in an n-by-n grid, so that each vertex is adjacent to the vertices that are not in the same row or column of the grid.</li></ul>
<h2 id="properties">Properties</h2>
The tensor product is the <a href="/facts/Product_(category_theory)/evFecz0t">category-theoretic product</a> in the category of graphs and <a href="/facts/Graph_homomorphism/XSljQ25z">graph homomorphisms</a>. That is, a homomorphism to G × H corresponds to a pair of homomorphisms to G and to H. In particular, a graph I admits a homomorphism into G × H if and only if it admits a homomorphism into G and into H.
To see that, in one direction, observe that a pair of homomorphisms fG : I → G and fH : I → H yields a homomorphism

{
            
              
                
                  f
                  :
                  I
                  →
                  G
                  ×
                  H
                
              
              
                
                  f
                  (
                  v
                  )
                  =
                  
                    (
                    
                      
                        f
                        
                          G
                        
                      
                      (
                      v
                      )
                      ,
                      
                        f
                        
                          H
                        
                      
                      (
                      v
                      )
                    
                    )
                  
                
              
            
            
          
        
      
    
    {\displaystyle {\begin{cases}f:I\to G\times H\\f(v)=\left(f_{G}(v),f_{H}(v)\right)\end{cases}}}

In the other direction, a homomorphism f : I → G × H can be composed with the projections homomorphisms

{
            
              
                
                  
                    π
                    
                      G
                    
                  
                  :
                  G
                  ×
                  H
                  →
                  G
                
              
              
                
                  
                    π
                    
                      G
                    
                  
                  (
                  (
                  u
                  ,
                  
                    u
                    ′
                  
                  )
                  )
                  =
                  u
                
              
            
            
          
        
        
        
        
          
            {
            
              
                
                  
                    π
                    
                      H
                    
                  
                  :
                  G
                  ×
                  H
                  →
                  H
                
              
              
                
                  
                    π
                    
                      H
                    
                  
                  (
                  (
                  u
                  ,
                  
                    u
                    ′
                  
                  )
                  )
                  =
                  
                    u
                    ′
                  
                
              
            
            
          
        
      
    
    {\displaystyle {\begin{cases}\pi _{G}:G\times H\to G\\\pi _{G}((u,u'))=u\end{cases}}\qquad \qquad {\begin{cases}\pi _{H}:G\times H\to H\\\pi _{H}((u,u'))=u'\end{cases}}}

to yield homomorphisms to G and to H.
The adjacency matrix of G × H is the <a href="/facts/Kronecker_product/gABGx6I6">Kronecker (tensor) product</a> of the <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrices</a> of G and H.
If a graph can be represented as a tensor product, then there may be multiple different representations (tensor products do not satisfy unique factorization) but each representation has the same number of irreducible factors. Imrich (1998) gives a polynomial time algorithm for recognizing tensor product graphs and finding a factorization of any such graph.
If either G or H is <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a>, then so is their tensor product. G × H is connected if and only if both factors are connected and at least one factor is nonbipartite.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> In particular the bipartite double cover of G is connected if and only if G is connected and nonbipartite.
The <a href="/facts/Hedetniemi_conjecture/FuvrM96u">Hedetniemi conjecture</a>, which gave a formula for the <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a> of a tensor product, was disproved by Yaroslav Shitov (2019).
The tensor product of graphs equips the category of graphs and graph homomorphisms with the structure of a <a href="/facts/Symmetric_monoidal_category/AxhumNny">symmetric</a> <a href="/facts/Closed_monoidal_category/FBe3ecNJ">closed monoidal category</a>. Let G0 denote the underlying set of vertices of the graph G. The internal hom [G, H] has functions f : G0 → H0 as vertices and an edge from f : G0 → H0 to f' : G0 → H0 whenever an edge {x, y} in G implies {f (x), f ' (y)} in H.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Graph_product/ru7rPMFW">Graph product</a></li>
<li><a href="/facts/Strong_product_of_graphs/aawyyHwy">Strong product of graphs</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of Morphisms of Graphs", The Electronic Journal of Combinatorics, 15: A1.</li>
<li>Hahn, Geňa; Sabidussi, Gert (1997), <a href="https://books.google.com/books?id=-tIaXdII8egC&pg=PA116">Graph symmetry: algebraic methods and applications</a>, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7923-4668-5.</li>
<li>Imrich, W. (1998), "Factoring cardinal product graphs in polynomial time", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 192: 119–144, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0012-365X%2898%2900069-7">10.1016/S0012-365X(98)00069-7</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1656730">1656730</a></li>
<li>Imrich, Wilfried; <a href="/facts/Sandi_Klav%25C5%25BEar/VjQD16Ps">Klavžar, Sandi</a> (2000), Product Graphs: Structure and Recognition, Wiley, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-37039-8</li>
<li>Shitov, Yaroslav (May 2019), Counterexamples to Hedetniemi's conjecture, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1905.02167">1905.02167</a></li>
<li>Weichsel, Paul M. (1962), "The Kronecker product of graphs", <a href="/facts/Proceedings_of_the_American_Mathematical_Society/W3wRF3MV">Proceedings of the American Mathematical Society</a>, 13 (1): 47–52, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2033769">10.2307/2033769</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2033769">2033769</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0133816">0133816</a></li>
<li><a href="/facts/Alfred_North_Whitehead/7KuylmP3">Whitehead, A. N.</a>; <a href="/facts/Bertrand_Russell/SRpwNX2U">Russell, B.</a> (1912), <a href="/facts/Principia_Mathematica/7ufeceV4">Principia Mathematica</a>, Cambridge University Press, vol. 2, p. 384</li></ul>
<h2 id="external-links">External links</h2>
<ul><li>Nicolas Bray. <a href="https://mathworld.wolfram.com/GraphTensorProduct.html">"Graph Tensor Product"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Weichsel 1962. - Weichsel, Paul M. (1962), "The Kronecker product of graphs", Proceedings of the American Mathematical Society, 13 (1): 47–52, doi:10.2307/2033769, JSTOR 2033769, MR 0133816 <a href="https://doi.org/10.2307%2F2033769" target="_blank">https://doi.org/10.2307%2F2033769</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hahn & Sabidussi 1997. - Hahn, Geňa; Sabidussi, Gert (1997), Graph symmetry: algebraic methods and applications, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, ISBN 978-0-7923-4668-5 <a href="https://books.google.com/books?id=-tIaXdII8egC&pg=PA116" target="_blank">https://books.google.com/books?id=-tIaXdII8egC&pg=PA116</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Imrich & Klavžar 2000, Theorem 5.29 - Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Brown et al. 2008; see also this proof - Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of Morphisms of Graphs", The Electronic Journal of Combinatorics, 15: A1 <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

Tensor product of graphs open-in-new

Tensor product of graphs