Community hub
0 subscribers8 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Tensor product of graphs.
Nothing was collected or created yet.
Tensor product of graphs
View on Wikipediafrom Wikipedia
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]- The tensor product G × K2 is a bipartite graph, called the bipartite double cover of G. The bipartite double cover of the Petersen graph is the Desargues graph: K2 × G(5,2) = G(10,3). The bipartite double cover of a complete graph Kn is a crown graph (a complete bipartite graph Kn,n minus a perfect matching).
- The tensor product of a complete graph with itself is the complement of a Rook's graph. 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.
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]- ^ Weichsel 1962.
- ^ Hahn & Sabidussi 1997.
- ^ Imrich & Klavžar 2000, Theorem 5.29
- ^ Brown et al. 2008; see also this proof
References
[edit]- Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of Morphisms of Graphs", The Electronic Journal of Combinatorics, 15: A1.
- 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.
- Imrich, W. (1998), "Factoring cardinal product graphs in polynomial time", Discrete Mathematics, 192: 119–144, doi:10.1016/S0012-365X(98)00069-7, MR 1656730
- Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
- Shitov, Yaroslav (May 2019), Counterexamples to Hedetniemi's conjecture, arXiv:1905.02167
- 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
- Whitehead, A. N.; Russell, B. (1912), Principia Mathematica, Cambridge University Press, vol. 2, p. 384
External links
[edit]- Nicolas Bray. "Graph Tensor Product". MathWorld.
Tensor product of graphs
View on Grokipediafrom Grokipedia
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 and , without loops or multiple edges, the tensor product is defined as the graph with vertex set , consisting of all ordered pairs where and .[5] The edge set is , meaning two vertices and are adjacent if and only if is adjacent to in and is adjacent to in .[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 and , , 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 on two vertices each is a graph with four vertices, labeled as pairs , , , , where and are adjacent in the first , and and 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: and . This yields two disjoint edges, or the matching . Similarly, the tensor product of the path graph (isomorphic to ) and produces the same structure: a graph on four vertices with two disjoint edges. The adjacency list for vertices ordered as , , , (where in ) confirms edges only between and . 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 and , with no edges) results in another edgeless graph on 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 and forms a graph on vertices arranged in an grid, where an edge connects to if and only if and . This structure is the complement of the Cartesian product , featuring no edges within the same row or column, and thus exhibits complete bipartite-like connections between distinct rows excluding matching columns. For , it reduces to the two disjoint edges described above, a disjoint union of complete bipartite graphs . Each vertex has degree .Notable products
The tensor product of two cycle graphs, , yields a circulant graph with vertices that inherits rotational symmetry from its factors, particularly when , in which case the product is itself circulant on the cyclic group of order . This structure arises because cycles are circulant graphs, and under coprimality, the connection sets combine to preserve the circulant form. For example, 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 -dimensional hypercube is constructed as the iterated Cartesian product of copies of , it differs from the tensor product construction; specifically, can be expressed as a tensor product if and only if , but iterated tensor products of beyond dimension 2 do not yield hypercubes.[12] For instance, , but is a disconnected 2-regular graph on 8 vertices, contrasting the connected 3-regular .[12] The tensor product of two complete bipartite graphs, such as , is bipartite, as the absence of odd cycles in each factor ensures no odd cycles in the product, which has vertex set size 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 and , denoted , is bipartite if and only if at least one of or is bipartite.[13] This property holds because the absence of odd cycles in the product depends on the factors: if both and contain odd cycles, then contains an odd-length cycle, for instance, of length equal to the least common multiple of the lengths of an odd cycle in and an odd cycle in , preserving the odd parity.[13] Conversely, if at least one factor, say , is bipartite with partite sets and , then can be properly 2-colored by assigning to each vertex the color of according to a proper 2-coloring of . The partite sets of are then and . No edges exist within these sets because has no edges within or , and edges in the product require adjacency in both factors, which would connect different partite sets in .[13] Regarding connectivity, assuming and are connected graphs, is connected if and only if at least one of or is non-bipartite.[13] When both are bipartite, 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 have partite sets and have . Vertices in 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., to ) or both in "odd" sets, while the other connects to . 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 , where each 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 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 of two graphs and is the product of their individual orders, given by .[16] This follows directly from the vertex set construction .[7] Similarly, the size of , or the number of edges , is the product of the sizes of and , expressed as . This arises because each edge in corresponds uniquely to a pair of edges, one from and one from .[16] The degree of a vertex in is the product of the degrees of in and in , so .[13] Consequently, the minimum degree and maximum degree are and , respectively. If is -regular and is -regular, then is -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 of two graphs and is the Kronecker product of their individual adjacency matrices, denoted . This representation captures the edges in , where vertices are pairs with and , and an edge exists between and if and only if there are edges in and in . The Kronecker product of two matrices of size and of size is a block matrix of size , where the -th block is the scalar times the entire matrix . 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 are all products , where ranges over the eigenvalues of and over those of , 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 on two vertices, with adjacency matrix , whose eigenvalues are and . The tensor product consists of two disjoint copies of on four vertices, with adjacency matrix whose eigenvalues are (multiplicity 2), (multiplicity 2)—precisely the products , , , and .Chromatic number
The chromatic number of the tensor product of graphs and satisfies , 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., for all finite simple graphs and .[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 .[10] Shitov's construction begins with a graph of girth greater than 6 and fractional chromatic number . For sufficiently large , define , the strong product of with the complete graph , yielding . Let . The exponential graph is then formed using -colorings of , resulting in . However, , as the tensor product admits a -coloring leveraging robust color classes and the high girth of 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 , with counterexamples for [18] and higher small values up to at least 13 as of 2022.[19] It holds when , including when at least one graph is bipartite (). The status remains open for products where at least one graph is planar ().[20] The clique number relates multiplicatively in other products but for the tensor product satisfies , 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 , 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 of graphs and serves as the categorical product in . This means that , equipped with the natural projection homomorphisms and defined by and , satisfies the universal property of the product. Specifically, for any graph and any graph homomorphisms and , there exists a unique graph homomorphism such that and . This is equivalent to the natural isomorphism of hom-sets where the isomorphism is induced by the projections. The projections and are indeed graph homomorphisms because they preserve adjacency: if and are adjacent in , then is an edge in and is an edge in , so and are adjacent in , and similarly for . This structure positions the tensor product as the fundamental product operation in , enabling the categorical study of graph homomorphisms and their preservation under products. In contrast, the coproduct in 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 , , and , there exists a natural isomorphism .[22] The unit object for this monoidal structure is the single-vertex graph , which satisfies the unit isomorphisms for any graph .[22] The category is symmetric, with a symmetry isomorphism defined by for vertices and , 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 and compatibility with the associator.[22] The structure is closed monoidal, with the internal hom (denoted ) given by the graph whose vertex set consists of all functions , and an edge between distinct functions and if, for every edge in , the vertices and are adjacent in . This construction ensures the tensor-hom adjunction , where denotes graph homomorphisms. The closure property of this monoidal category enables the formation of exponential objects, such as , which captures the structure of mappings from to equipped with the induced graph relations, allowing iterated applications like .[22]Comparisons and extensions
Relation to other graph products
The tensor product of two graphs and , also known as the direct or categorical product, differs from the Cartesian product in its edge formation rule. In the tensor product , an edge exists between vertices and only if is adjacent to in and is adjacent to in , requiring simultaneous adjacency in both factors.[23] By contrast, the Cartesian product connects to if either and is adjacent to in , or and is adjacent to in , 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 .[23] The strong product combines elements of both, with edges comprising the union of those in and .[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 introduces asymmetry, connecting to if is adjacent to in , or if and is adjacent to in .[23] This can be viewed as a directed variant where dominates, attaching a full copy of to each vertex of and linking copies based on '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 and edge set the union of and , without inter-component connections. The following table compares these products using the complete graph (a single edge) as an example, illustrating vertex sets, edge conditions, and outcomes:| Product | Vertex Set | Edge Condition | Example |
|---|---|---|---|
| Tensor () | Adjacent in both and | (two disjoint edges) | |
| Cartesian () | Adjacent in one and identical in the other | (4-cycle)[23] | |
| Strong () | Union of tensor and Cartesian conditions | (complete on 4 vertices)[23] | |
| Lexicographic () | Adjacent in , or identical in and adjacent in | (complete on 4 vertices) | |
| Disjoint Union | Edges within each component only | Two disjoint |