Hubbry Logo
search
logo
Tensor product of graphs avatar
Tensor product of graphs
Tensor product of graphs
current hub
1933129

Tensor product of graphs

logo
Community Hub0 Subscribers
Read side by side
Tensor product of graphs
View on Wikipedia
from Wikipedia
The tensor product of graphs.

In graph theory, the tensor product G × H of graphs G and H is a graph such that

  • the vertex set of G × H is the Cartesian product V(G) × V(H); and
  • vertices (g,h) and (g',h' ) are adjacent in G × H if and only if
    • g is adjacent to g' in G, and
    • h is adjacent to h' in H.

The tensor product is also called the direct product, Kronecker product, categorical product, cardinal product, relational product, weak direct product, or conjunction. As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1912). It is also equivalent to the Kronecker product of the adjacency matrices of the graphs.[1]

The notation G × H is also (and formerly normally was) used to represent another construction known as the Cartesian product of graphs, but nowadays more commonly refers to the tensor product. The cross symbol shows visually the two edges resulting from the tensor product of two edges.[2] This product should not be confused with the strong product of graphs.

Examples

[edit]

Properties

[edit]

The tensor product is the category-theoretic product in the category of graphs and graph homomorphisms. 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

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

to yield homomorphisms to G and to H.

The adjacency matrix of G × H is the Kronecker (tensor) product of the adjacency matrices 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 bipartite, 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.[3] In particular the bipartite double cover of G is connected if and only if G is connected and nonbipartite.

The Hedetniemi conjecture, which gave a formula for the chromatic number 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 symmetric closed monoidal category. 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.[4]

See also

[edit]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Tensor product of graphs

View on Grokipedia
from Grokipedia
In graph theory, the tensor product of two graphs GG and HH, denoted G×HG \times H, is a graph product whose vertex set is the Cartesian product V(G)×V(H)V(G) \times V(H), and in which two vertices (u,v)(u, v) and (u′,v′)(u', v') are adjacent if and only if uu is adjacent to u′u' in GG and vv is adjacent to v′v' in HH. This operation, originally termed the Kronecker product, was introduced by Paul M. Weichsel in 1962 as a construction derived from the Kronecker product of the graphs' adjacency matrices, where the adjacency matrix of G×HG \times H is precisely the Kronecker product A(G)⊗A(H)A(G) \otimes A(H). It is also known by several alternative names, including the direct product, categorical product, cardinal product, conjunction, and weak direct product, reflecting its roles in various categorical and algebraic contexts within graph theory. The tensor product is both commutative (G×H≅H×GG \times H \cong H \times G) and associative ((G×H)×K≅G×(H×K)(G \times H) \times K \cong G \times (H \times K)), properties that mirror those of the underlying matrix operation and facilitate the study of multiple graph products. A fundamental connectivity result states that G×HG \times H is connected if and only if at least one of GG or HH contains an odd-length cycle; conversely, if both graphs are bipartite (i.e., contain no odd cycles), then G×HG \times H consists of exactly two connected components. For instance, the tensor product G×K2G \times K_2 yields the bipartite double cover of GG, a construction with applications in distinguishing vertices via walks.[1] Beyond basic structural properties, the tensor product plays a significant role in spectral graph theory, where the eigenvalues of the product graph are all possible products of eigenvalues of the factors, aiding analysis of graph spectra and expanders.[2] It also arises in the study of graph homomorphisms and category theory, serving as the monoidal product in the category of graphs with homomorphisms as morphisms.[3] Applications extend to quantum computing, such as modeling quantum walks on product graphs, and to algorithmic problems like factoring product graphs in polynomial time.[2]

Fundamentals

Definition

The tensor product of graphs, also referred to as the direct product or categorical product, is a binary operation that constructs a new graph from two given graphs by combining their structures such that adjacency in the resulting graph requires simultaneous adjacency in both input graphs.[4] This operation preserves the adjacency relations across components, providing a way to model interactions where edges emerge only from coordinated connections in the originals, which has applications in areas like network analysis and combinatorial optimization.[5] Formally, for two undirected simple graphs $ G = (V_G, E_G) $ and $ H = (V_H, E_H) $, without loops or multiple edges, the tensor product $ G \times H $ is defined as the graph with vertex set $ V(G \times H) = V_G \times V_H $, consisting of all ordered pairs $ (u, v) $ where $ u \in V_G $ and $ v \in V_H $.[5] The edge set is $ E(G \times H) = { ((u,v), (u',v')) \mid (u,u') \in E_G \text{ and } (v,v') \in E_H } $, meaning two vertices $ (u,v) $ and $ (u',v') $ are adjacent if and only if $ u $ is adjacent to $ u' $ in $ G $ and $ v $ is adjacent to $ v' $ in $ H $.[5] This construction extends naturally to directed graphs by considering directed edges, but the standard definition assumes undirected simple graphs unless otherwise specified.[1] As an operation on binary relations, the tensor product underlying this graph product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica.[4] In the context of graph theory, the product was formalized by Weichsel, who established its basic properties including the adjacency matrix representation via the Kronecker product.[5]

Historical background

The tensor product of graphs originated as an operation on binary relations introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica, a foundational work in mathematical logic published in three volumes from 1910 to 1913. In this context, the construction served to combine relations logically, providing an early combinatorial framework that later extended to graphs viewed as symmetric binary relations on vertex sets.[6] Early applications in graph theory emerged in the mid-20th century amid growing interest in combinatorial structures. Gert Sabidussi formalized the tensor product—also termed the direct product—in his 1959 paper "Graph Multiplication," where he defined it explicitly for graphs and explored its properties in relation to graph homomorphisms and automorphisms.[7] Sabidussi's work highlighted naming variations, such as "categorical product" or "Kronecker product," reflecting its algebraic analogies, and established it as a key tool for studying graph symmetries and decompositions.[8] Throughout the 1960s, the tensor product gained prominence in combinatorial graph theory and category theory, with researchers adopting it to model complex relational structures. Sabidussi further advanced its categorical perspective in subsequent papers on graph homomorphisms, integrating it into the category of graphs where it serves as the categorical product.[9] A pivotal milestone came in 1966 when Stephen Hedetniemi formulated his famous conjecture on the chromatic number of tensor products in his PhD thesis, positing that for any graphs GG and HH, χ(G×H)=min⁡{χ(G),χ(H)}\chi(G \times H) = \min\{\chi(G), \chi(H)\}, which spurred decades of research into coloring properties.[10] The conjecture remained unsolved for over 50 years until it was disproved in 2019 by the construction of counterexamples.[10] This underscored the product's role in extremal graph theory.[11]

Examples

Basic examples

The tensor product of two copies of the complete graph K2K_2 on two vertices each is a graph with four vertices, labeled as pairs (u,a)(u,a), (u,b)(u,b), (v,a)(v,a), (v,b)(v,b), where uu and vv are adjacent in the first K2K_2, and aa and bb are adjacent in the second. An edge exists between pairs only if both components are adjacent in their respective graphs, resulting in exactly two edges: (u,a)−(v,b)(u,a)-(v,b) and (u,b)−(v,a)(u,b)-(v,a). This yields two disjoint edges, or the matching 2K22K_2. Similarly, the tensor product of the path graph P2P_2 (isomorphic to K2K_2) and K2K_2 produces the same structure: a graph on four vertices with two disjoint edges. The adjacency list for vertices ordered as (1,a)(1,a), (1,b)(1,b), (2,a)(2,a), (2,b)(2,b) (where 1∼21 \sim 2 in P2P_2) confirms edges only between (1,a)−(2,b)(1,a)-(2,b) and (1,b)−(2,a)(1,b)-(2,a). This simple case highlights how the tensor product requires simultaneous adjacency in both factors, leading to a disconnected graph with no cycles. The tensor product of two edgeless graphs (empty graphs Km‾\overline{K_m} and Kn‾\overline{K_n}, with no edges) results in another edgeless graph on mnmn vertices, as there are no adjacent pairs in either factor to generate edges in the product. In contrast, the tensor product of two complete graphs KmK_m and KnK_n forms a graph on mnmn vertices arranged in an m×nm \times n grid, where an edge connects (i,j)(i,j) to (k,l)(k,l) if and only if i≠ki \neq k and j≠lj \neq l. This structure is the complement of the Cartesian product Km□KnK_m \square K_n, featuring no edges within the same row or column, and thus exhibits complete bipartite-like connections between distinct rows excluding matching columns. For m=n=2m=n=2, it reduces to the two disjoint edges described above, a disjoint union of complete bipartite graphs K1,1K_{1,1}. Each vertex has degree (m−1)(n−1)(m-1)(n-1).

Notable products

The tensor product of two cycle graphs, Cm×CnC_m \times C_n, yields a circulant graph with mnmn vertices that inherits rotational symmetry from its factors, particularly when gcd⁡(m,n)=1\gcd(m,n)=1, in which case the product is itself circulant on the cyclic group of order mnmn. This structure arises because cycles are circulant graphs, and under coprimality, the connection sets combine to preserve the circulant form. For example, C3×C3C_3 \times C_3 forms a 4-regular circulant graph on 9 vertices, distinct from the toroidal grid obtained via Cartesian product. The tensor product of the Petersen graph with itself produces a 9-regular graph on 100 vertices, as the Petersen graph is 3-regular and degrees multiply under the tensor operation. This resulting graph maintains high symmetry due to the automorphism group of the Petersen graph. Although the nn-dimensional hypercube QnQ_n is constructed as the iterated Cartesian product of nn copies of K2K_2, it differs from the tensor product construction; specifically, QkQ_k can be expressed as a tensor product G×K2G \times K_2 if and only if G≅Qk−1G \cong Q_{k-1}, but iterated tensor products of K2K_2 beyond dimension 2 do not yield hypercubes.[12] For instance, K2×K2≅C4≅Q2K_2 \times K_2 \cong C_4 \cong Q_2, but C4×K2C_4 \times K_2 is a disconnected 2-regular graph on 8 vertices, contrasting the connected 3-regular Q3Q_3.[12] The tensor product of two complete bipartite graphs, such as Km,n×Kp,qK_{m,n} \times K_{p,q}, is bipartite, as the absence of odd cycles in each factor ensures no odd cycles in the product, which has vertex set size mn⋅pqmn \cdot pq and edges only between appropriately partitioned subsets. This property holds more generally for the tensor product of any two bipartite graphs, though the result is typically disconnected with two isomorphic components.

Structural properties

Connectivity and bipartiteness

The tensor product of two graphs GG and HH, denoted G×HG \times H, is bipartite if and only if at least one of GG or HH is bipartite.[13] This property holds because the absence of odd cycles in the product depends on the factors: if both GG and HH contain odd cycles, then G×HG \times H contains an odd-length cycle, for instance, of length equal to the least common multiple of the lengths of an odd cycle in GG and an odd cycle in HH, preserving the odd parity.[13] Conversely, if at least one factor, say HH, is bipartite with partite sets XX and YY, then G×HG \times H can be properly 2-colored by assigning to each vertex (u,v)(u, v) the color of vv according to a proper 2-coloring of HH. The partite sets of G×HG \times H are then V(G)×XV(G) \times X and V(G)×YV(G) \times Y. No edges exist within these sets because HH has no edges within XX or YY, and edges in the product require adjacency in both factors, which would connect different partite sets in HH.[13] Regarding connectivity, assuming GG and HH are connected graphs, G×HG \times H is connected if and only if at least one of GG or HH is non-bipartite.[13] When both are bipartite, G×HG \times H is disconnected and consists of exactly two connected components.[14] Each component is itself bipartite and isomorphic under certain automorphisms of the factors, such as those interchanging partite sets.[15] A proof sketch for connectivity relies on analyzing the connected components via parity signatures from the bipartitions. Let GG have partite sets A∪BA \cup B and HH have C∪DC \cup D. Vertices in G×HG \times H can be grouped by the parity of their coordinates: one component consists of edges connecting vertices where both coordinates are in "even" sets (e.g., A×CA \times C to B×DB \times D) or both in "odd" sets, while the other connects A×DA \times D to B×CB \times C. No edges exist between these two groupings because an edge in the product flips the partite set in both factors simultaneously, preserving the relative parity within each group but not crossing between them. If at least one factor is non-bipartite, an odd cycle in that factor allows paths to bridge the parity groups, rendering the product connected.[13] For example, consider the tensor product of two paths P3×P3P_3 \times P_3, where each P3P_3 is bipartite. This yields two disconnected components, each a bipartite graph isomorphic to a grid-like structure without odd cycles. Similarly, the product of two even cycles C4×C4C_4 \times C_4 is disconnected with two components, illustrating how the tensor product fails to connect when both factors lack odd cycles.[14]

Degree and order

The order of the tensor product G×HG \times H of two graphs GG and HH is the product of their individual orders, given by ∣V(G×H)∣=∣V(G)∣×∣V(H)∣|V(G \times H)| = |V(G)| \times |V(H)|.[16] This follows directly from the vertex set construction V(G×H)=V(G)×V(H)V(G \times H) = V(G) \times V(H).[7] Similarly, the size of G×HG \times H, or the number of edges ∣E(G×H)∣|E(G \times H)|, is the product of the sizes of GG and HH, expressed as ∣E(G×H)∣=∣E(G)∣×∣E(H)∣|E(G \times H)| = |E(G)| \times |E(H)|. This arises because each edge in G×HG \times H corresponds uniquely to a pair of edges, one from GG and one from HH.[16] The degree of a vertex (u,v)(u, v) in G×HG \times H is the product of the degrees of uu in GG and vv in HH, so deg⁡G×H((u,v))=deg⁡G(u)×deg⁡H(v)\deg_{G \times H}((u, v)) = \deg_G(u) \times \deg_H(v).[13] Consequently, the minimum degree δ(G×H)\delta(G \times H) and maximum degree Δ(G×H)\Delta(G \times H) are δ(G)×δ(H)\delta(G) \times \delta(H) and Δ(G)×Δ(H)\Delta(G) \times \Delta(H), respectively. If GG is rr-regular and HH is ss-regular, then G×HG \times H is (rs)(r s)-regular, preserving regularity under the product operation.[13] These formulas highlight how the tensor product scales the structural measures multiplicatively, influencing applications in network modeling and combinatorial analysis.

Algebraic properties

Adjacency matrix

The adjacency matrix of the tensor product G×HG \times H of two graphs GG and HH is the Kronecker product of their individual adjacency matrices, denoted A(G×H)=A(G)⊗A(H)A(G \times H) = A(G) \otimes A(H). This representation captures the edges in G×HG \times H, where vertices are pairs (u,v)(u, v) with u∈V(G)u \in V(G) and v∈V(H)v \in V(H), and an edge exists between (u1,v1)(u_1, v_1) and (u2,v2)(u_2, v_2) if and only if there are edges u1u2u_1 u_2 in GG and v1v2v_1 v_2 in HH. The Kronecker product of two matrices A=(aij)A = (a_{ij}) of size m×nm \times n and BB of size p×qp \times q is a block matrix of size mp×nqmp \times nq, where the (i,j)(i, j)-th block is the scalar aija_{ij} times the entire matrix BB. For adjacency matrices, this structure ensures that the resulting matrix encodes the combined adjacency relations precisely, preserving the binary nature of graph edges (0 or 1 entries). A key spectral implication is that the eigenvalues of A(G×H)A(G \times H) are all products λμ\lambda \mu, where λ\lambda ranges over the eigenvalues of A(G)A(G) and μ\mu over those of A(H)A(H), with algebraic multiplicities given by the product of the individual multiplicities. This property facilitates the analysis of spectral features in product graphs without direct computation of the large matrix. For example, consider the path graph P2P_2 on two vertices, with adjacency matrix A(P2)=(0110)A(P_2) = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, whose eigenvalues are 11 and −1-1. The tensor product P2×P2P_2 \times P_2 consists of two disjoint copies of K2K_2 on four vertices, with adjacency matrix
A(P2×P2)=(0001001001001000), A(P_2 \times P_2) = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix},
whose eigenvalues are 11 (multiplicity 2), −1-1 (multiplicity 2)—precisely the products 1⋅1=11 \cdot 1 = 1, 1⋅(−1)=−11 \cdot (-1) = -1, (−1)⋅1=−1(-1) \cdot 1 = -1, and (−1)⋅(−1)=1(-1) \cdot (-1) = 1.

Chromatic number

The chromatic number χ(G×H)\chi(G \times H) of the tensor product of graphs GG and HH satisfies χ(G×H)≤min⁡{χ(G),χ(H)}\chi(G \times H) \leq \min\{\chi(G), \chi(H)\}, as a proper coloring of the factor with the smaller chromatic number induces a proper coloring of the product via projection onto that factor.[10] In 1966, Stephen Hedetniemi conjectured that equality always holds, i.e., χ(G×H)=min⁡{χ(G),χ(H)}\chi(G \times H) = \min\{\chi(G), \chi(H)\} for all finite simple graphs GG and HH.[17] This long-standing conjecture motivated extensive research into coloring properties of graph products. The conjecture was disproved in 2019 by Yaroslav Shitov, who constructed explicit counterexamples where χ(G×H)<min⁡{χ(G),χ(H)}\chi(G \times H) < \min\{\chi(G), \chi(H)\}.[10] Shitov's construction begins with a graph Γ\Gamma of girth greater than 6 and fractional chromatic number χf(Γ)>3.1\chi_f(\Gamma) > 3.1. For sufficiently large qq, define H=Γ⊠KqH = \Gamma \boxtimes K_q, the strong product of Γ\Gamma with the complete graph KqK_q, yielding χ(H)>3.1q\chi(H) > 3.1q. Let c=⌈3.1q⌉c = \lceil 3.1q \rceil. The exponential graph Ec(H)E_c(H) is then formed using cc-colorings of HH, resulting in χ(Ec(H))>c\chi(E_c(H)) > c. However, χ(H×Ec(H))=c<min⁡{χ(H),χ(Ec(H))}\chi(H \times E_c(H)) = c < \min\{\chi(H), \chi(E_c(H))\}, as the tensor product admits a cc-coloring leveraging robust color classes and the high girth of Γ\Gamma to avoid monochromatic edges in certain substructures. This yields counterexamples for arbitrarily large chromatic numbers.[10] Subsequent work has shown that the conjecture fails for all min⁡{χ(G),χ(H)}≥4\min\{\chi(G), \chi(H)\} \geq 4, with counterexamples for min⁡χ=4\min \chi = 4[18] and higher small values up to at least 13 as of 2022.[19] It holds when min⁡{χ(G),χ(H)}≤3\min\{\chi(G), \chi(H)\} \leq 3, including when at least one graph is bipartite (χ=2\chi = 2). The status remains open for products where at least one graph is planar (χ≤4\chi \leq 4).[20] The clique number relates multiplicatively in other products but for the tensor product satisfies ω(G×H)=min⁡{ω(G),ω(H)}\omega(G \times H) = \min\{\omega(G), \omega(H)\}, as any clique in the product projects to cliques of equal size in both factors, with no repeated coordinates possible due to the absence of loops.[21]

Categorical aspects

Graph homomorphism product

In the category of graphs, denoted \Grph\Grph, the objects are graphs and the morphisms are graph homomorphisms, which are vertex mappings that preserve adjacency (i.e., map adjacent vertices to adjacent vertices). The tensor product G×HG \times H of graphs GG and HH serves as the categorical product in \Grph\Grph. This means that G×HG \times H, equipped with the natural projection homomorphisms πG:G×H→G\pi_G: G \times H \to G and πH:G×H→H\pi_H: G \times H \to H defined by πG(u,v)=u\pi_G(u,v) = u and πH(u,v)=v\pi_H(u,v) = v, satisfies the universal property of the product. Specifically, for any graph KK and any graph homomorphisms f:K→Gf: K \to G and g:K→Hg: K \to H, there exists a unique graph homomorphism ϕ:K→G×H\phi: K \to G \times H such that πG∘ϕ=f\pi_G \circ \phi = f and πH∘ϕ=g\pi_H \circ \phi = g. This is equivalent to the natural isomorphism of hom-sets
\Hom\Grph(K,G×H)≅\Hom\Grph(K,G)×\Hom\Grph(K,H), \Hom_{\Grph}(K, G \times H) \cong \Hom_{\Grph}(K, G) \times \Hom_{\Grph}(K, H),
where the isomorphism is induced by the projections. The projections πG\pi_G and πH\pi_H are indeed graph homomorphisms because they preserve adjacency: if (u1,v1)(u_1, v_1) and (u2,v2)(u_2, v_2) are adjacent in G×HG \times H, then u1u2u_1 u_2 is an edge in GG and v1v2v_1 v_2 is an edge in HH, so πG(u1,v1)=u1\pi_G(u_1, v_1) = u_1 and πG(u2,v2)=u2\pi_G(u_2, v_2) = u_2 are adjacent in GG, and similarly for πH\pi_H. This structure positions the tensor product as the fundamental product operation in \Grph\Grph, enabling the categorical study of graph homomorphisms and their preservation under products. In contrast, the coproduct in \Grph\Grph is the disjoint union of graphs, which satisfies a dual universal property involving homomorphisms into the union rather than out of it.

Monoidal category

The category of graphs and graph homomorphisms, equipped with the tensor product (also known as the direct product), forms a symmetric monoidal category.[22] The tensor product is associative up to isomorphism, meaning that for any graphs $ G $, $ H $, and $ K $, there exists a natural isomorphism $ (G \times H) \times K \cong G \times (H \times K) $.[22] The unit object for this monoidal structure is the single-vertex graph $ K_1 $, which satisfies the unit isomorphisms $ G \times K_1 \cong G \cong K_1 \times G $ for any graph $ G $.[22] The category is symmetric, with a symmetry isomorphism $ \sigma_{G,H}: G \times H \to H \times G $ defined by $ \sigma_{G,H}((u,v)) = (v,u) $ for vertices $ u \in V(G) $ and $ v \in V(H) $, preserving edges since adjacency in the tensor product requires simultaneous adjacency in both factors.[22] This isomorphism satisfies the standard axioms for braiding in a symmetric monoidal category, including $ \sigma_{H,G} \circ \sigma_{G,H} = \mathrm{id}_{G \times H} $ and compatibility with the associator.[22] The structure is closed monoidal, with the internal hom $ [G, H] $ (denoted $ G \multimap H $) given by the graph whose vertex set consists of all functions $ f: V(G) \to V(H) $, and an edge between distinct functions $ f $ and $ g $ if, for every edge $ xy $ in $ G $, the vertices $ f(x) $ and $ g(y) $ are adjacent in $ H $. This construction ensures the tensor-hom adjunction $ \mathrm{Hom}(G \times H, K) \cong \mathrm{Hom}(G, [H, K]) $, where $ \mathrm{Hom} $ denotes graph homomorphisms. The closure property of this monoidal category enables the formation of exponential objects, such as $ H^G \cong [G, H] $, which captures the structure of mappings from $ G $ to $ H $ equipped with the induced graph relations, allowing iterated applications like $ H^{G \times K} \cong [G \times K, H] \cong [G, [K, H]] $.[22]

Comparisons and extensions

Relation to other graph products

The tensor product of two graphs GG and HH, also known as the direct or categorical product, differs from the Cartesian product G□HG \square H in its edge formation rule. In the tensor product G×HG \times H, an edge exists between vertices (u,v)(u, v) and (u′,v′)(u', v') only if uu is adjacent to u′u' in GG and vv is adjacent to v′v' in HH, requiring simultaneous adjacency in both factors.[23] By contrast, the Cartesian product connects (u,v)(u, v) to (u′,v′)(u', v') if either u=u′u = u' and vv is adjacent to v′v' in HH, or v=v′v = v' and uu is adjacent to u′u' in GG, allowing edges along one dimension while fixing the other.[23] This makes the tensor product stricter, often resulting in sparser graphs than the Cartesian product for the same vertex set V(G)×V(H)V(G) \times V(H).[23] The strong product G⊠HG \boxtimes H combines elements of both, with edges comprising the union of those in G×HG \times H and G□HG \square H.[23] Thus, it includes all connections from the tensor product plus additional edges from the Cartesian product, yielding a denser graph that subsumes both as subgraphs.[23] Unlike the commutative and associative tensor and Cartesian products, the strong product shares these properties but emphasizes the "strongest" connectivity between factors. The lexicographic product G∘HG \circ H introduces asymmetry, connecting (u,v)(u, v) to (u′,v′)(u', v') if uu is adjacent to u′u' in GG, or if u=u′u = u' and vv is adjacent to v′v' in HH.[23] This can be viewed as a directed variant where GG dominates, attaching a full copy of HH to each vertex of GG and linking copies based on GG's edges, leading to non-commutative results unlike the tensor product.[23] In categorical terms, the disjoint union serves as the coproduct in the category of graphs, forming the graph with vertex set V(G)⊔V(H)V(G) \sqcup V(H) and edge set the union of E(G)E(G) and E(H)E(H), without inter-component connections. The following table compares these products using the complete graph K2K_2 (a single edge) as an example, illustrating vertex sets, edge conditions, and outcomes:
ProductVertex SetEdge ConditionK2K_2 Example
Tensor (×\times)V(G)×V(H)V(G) \times V(H)Adjacent in both GG and HH2K22K_2 (two disjoint edges)
Cartesian (□\square)V(G)×V(H)V(G) \times V(H)Adjacent in one and identical in the otherC4C_4 (4-cycle)[23]
Strong (⊠\boxtimes)V(G)×V(H)V(G) \times V(H)Union of tensor and Cartesian conditionsK4K_4 (complete on 4 vertices)[23]
Lexicographic (∘\circ)V(G)×V(H)V(G) \times V(H)Adjacent in GG, or identical in GG and adjacent in HHK4K_4 (complete on 4 vertices)
Disjoint UnionV(G)⊔V(H)V(G) \sqcup V(H)Edges within each component onlyTwo disjoint K2K_2

Factorization and computation

A polynomial-time algorithm exists for recognizing tensor products of graphs and computing their prime factorizations, applicable to finite connected non-bipartite graphs. Developed by Imrich, this method decomposes a graph into irreducible factors under the tensor product by analyzing neighborhood structures and ensuring uniqueness up to isomorphism and factor order.[24] The algorithm runs in polynomial time relative to the number of vertices, enabling efficient identification of product decompositions without exhaustive enumeration.[24] Central to this approach is the unique factorization theorem for tensor products: every connected non-bipartite graph admits a unique prime factorization, where the factors are prime with respect to the tensor product and the decomposition is unique up to isomorphism and permutation of factors.[24] This theorem, also established by Imrich, guarantees that the output of the recognition algorithm yields the canonical decomposition, facilitating further structural analysis. Bipartite graphs, however, lack this uniqueness, as multiple factorizations may exist due to the presence of even cycles.[24] The computational complexity of tensor product factorization is generally high: determining primality (i.e., whether a graph is irreducible under the tensor product) is graph isomorphism-hard, even for connected non-bipartite graphs in certain subclasses.[25] This GI-hardness arises from reductions showing that factorization problems encode graph isomorphism instances. Nonetheless, for graphs with bounded maximum degree, the problem becomes tractable in polynomial time, as isomorphism testing in bounded-degree graphs is solvable efficiently, and the factorization leverages similar structural invariants.[25] These factorization techniques have practical applications in graph databases, where decomposing networks into tensor factors reveals modular structures underlying complex relational data. In network analysis, they aid in modeling large-scale systems like social or communication networks via Kronecker (tensor) products, allowing sparse representations and scalable simulations of emergent topologies.[24]
User Avatar
No comments yet.