Cartesian product of graphs

Last updated

In graph theory, the Cartesian productG$\square$ H of graphs G and H is a graph such that In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Contents

• the vertex set of G$\square$ H is the Cartesian product V(G) × V(H); and
• two vertices (u,u' ) and (v,v' ) are adjacent in G$\square$ H if and only if either
• u = v and u' is adjacent to v' in H, or
• u' = v' and u is adjacent to v in G. In set theory, a Cartesian product is a mathematical operation that returns a set from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where aA and bB. Products can be specified using set-builder notation, e.g.

The operation is associative, as the graphs (F$\square$ G) $\square$ H and F$\square$ (G$\square$ H) are naturally isomorphic. The operation is commutative as an operation on isomorphism classes of graphs, and more strongly the graphs G$\square$ H and H$\square$ G are naturally isomorphic, but it is not commutative as an operation on labeled graphs. In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H In mathematics, when the elements of some set S have a notion of equivalence defined on them, then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a and b belong to the same equivalence class if and only if a and b are equivalent.

The notation G × H has often been used for Cartesian products of graphs, but is now more commonly used for another construction known as the tensor product of graphs. The square symbol is an intuitive and unambiguous notation for the Cartesian product, since it shows visually the four edges resulting from the Cartesian product of two edges. In graph theory, the tensor productG × H of graphs G and H is a graph such that

Examples

• The Cartesian product of two edges is a cycle on four vertices: K2$\square$ K2 = C4.
• The Cartesian product of K2 and a path graph is a ladder graph.
• The Cartesian product of two path graphs is a grid graph.
• The Cartesian product of n edges is a hypercube: In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in Cn equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.

In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are {vi, vi+1} where i = 1, 2, …, n − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices, while all others have degree 2. In the mathematical field of graph theory, the ladder graphLn is a planar undirected graph with 2n vertices and 3n-2 edges.

$(K_{2})^{\square n}=Q_{n}.$ Thus, the Cartesian product of two hypercube graphs is another hypercube: Qi$\square$ Qj = Qi+j.
• The Cartesian product of two median graphs is another median graph.
• The graph of vertices and edges of an n-prism is the Cartesian product graph K2$\square$ Cn.
• The rook's graph is the Cartesian product of two complete graphs. In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c. In geometry, a prism is a polyhedron comprising an n-sided polygonal base, a second base which is a translated copy of the first, and n other faces joining corresponding sides of the two bases. All cross-sections parallel to the bases are translations of the bases. Prisms are named for their bases, so a prism with a pentagonal base is called a pentagonal prism. The prisms are a subclass of the prismatoids. In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge represents a legal move from one square to another. The same graphs can be defined mathematically as the Cartesian products of two complete graphs or as the line graphs of complete bipartite graphs.

Properties

If a connected graph is a Cartesian product, it can be factorized uniquely as a product of prime factors, graphs that cannot themselves be decomposed as products of graphs.  However, Imrich & Klavžar (2000) describe a disconnected graph that can be expressed in two different ways as a Cartesian product of prime graphs:

(K1 + K2 + K22) $\square$ (K1 + K23) = (K1 + K22 + K24) $\square$ (K1 + K2),

where the plus sign denotes disjoint union and the superscripts denote exponentiation over Cartesian products.

A Cartesian product is vertex transitive if and only if each of its factors is. 

A Cartesian product is bipartite if and only if each of its factors is. More generally, the chromatic number of the Cartesian product satisfies the equation

χ(G $\square$ H) = max {χ(G), χ(H)}. 

The Hedetniemi conjecture states a related equality for the tensor product of graphs. The independence number of a Cartesian product is not so easily calculated, but as Vizing (1963) showed it satisfies the inequalities

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G$\square$ H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

The Vizing conjecture states that the domination number of a Cartesian product satisfies the inequality

γ(G$\square$ H) ≥ γ(G)γ(H).

Cartesian product graphs can be recognized efficiently, in linear time. 

Algebraic graph theory

Algebraic graph theory can be used to analyse the Cartesian graph product. If the graph $G_{1}$ has $n_{1}$ vertices and the $n_{1}\times n_{1}$ adjacency matrix $\mathbf {A} _{1}$ , and the graph $G_{2}$ has $n_{2}$ vertices and the $n_{2}\times n_{2}$ adjacency matrix $\mathbf {A} _{2}$ , then the adjacency matrix of the Cartesian product of both graphs is given by

$\mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}$ ,

where $\otimes$ denotes the Kronecker product of matrices and $\mathbf {I} _{n}$ denotes the $n\times n$ identity matrix.  The adjacency matrix of the Cartesian graph product is therefore the Kronecker sum of the adjacency matrices of the factors.

History

According to Imrich & Klavžar (2000), Cartesian products of graphs were defined in 1912 by Whitehead and Russell. They were repeatedly rediscovered later, notably by GertSabidussi  ( 1960 ).

1. Imrich & Klavžar (2000), Theorem 4.19.
2. Imrich & Peterin (2007). For earlier polynomial time algorithms see Feigenbaum, Hershberger & Schäffer (1985) and Aurenhammer, Hagauer & Imrich (1992).