Cartesian product of graphs

Last updated
The Cartesian product of graphs. Graph-Cartesian-product.svg
The Cartesian product of graphs.

In graph theory, the Cartesian productGH of graphs G and H is a graph such that

Graph theory study of graphs, which are mathematical structures used to model pairwise relations between objects

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

Cartesian product set of the ordered pairs such that the first element of the pair is in the first element of the product and the second element of the pair is in the second element of the product

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 (FG) H and F (GH) are naturally isomorphic. The operation is commutative as an operation on isomorphism classes of graphs, and more strongly the graphs GH and HG are naturally isomorphic, but it is not commutative as an operation on labeled graphs.

Graph isomorphism

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

Equivalence class mathematical concept

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. [1]

Tensor product of graphs

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

Examples

Cycle graph graph that consists of a single cycle

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.

Ladder graph planar undirected graph with 2n vertices and 3n-2 edges; the Cartesian product of two path graphs, one of which has only one edge

In the mathematical field of graph theory, the ladder graphLn is a planar undirected graph with 2n vertices and 3n-2 edges.

Thus, the Cartesian product of two hypercube graphs is another hypercube: Qi Qj = Qi+j.
Median graph

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.

Prism (geometry) geometric shape, a polyhedron with an n-sided polygonal base

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.

Rooks graph graph that represents all legal moves of the rook chess piece on a chessboard

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. [2] 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) (K1 + K23) = (K1 + K22 + K24) (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. [3]

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 H) = max {χ(G), χ(H)}. [4]

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)} ≤ α(GH) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

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

γ(GH) ≥ γ(G)γ(H).

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

Algebraic graph theory

Algebraic graph theory can be used to analyse the Cartesian graph product. If the graph has vertices and the adjacency matrix , and the graph has vertices and the adjacency matrix , then the adjacency matrix of the Cartesian product of both graphs is given by

,

where denotes the Kronecker product of matrices and denotes the identity matrix. [6] 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 ).

Notes

  1. Hahn & Sabidussi (1997).
  2. Sabidussi (1960); Vizing (1963).
  3. Imrich & Klavžar (2000), Theorem 4.19.
  4. Sabidussi (1957).
  5. Imrich & Peterin (2007). For earlier polynomial time algorithms see Feigenbaum, Hershberger & Schäffer (1985) and Aurenhammer, Hagauer & Imrich (1992).
  6. Kaveh & Rahami (2005).

Related Research Articles

Cayley graph graph whose vertices and edges represent the elements of a group and their products with the generators of the group

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group. It is a central tool in combinatorial and geometric group theory.

Total coloring

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges and no edge and its endvertices are assigned the same color. The total chromatic number χ″(G) of a graph G is the least number of colors needed in any total coloring of G.

In the mathematical field of graph theory, the Laplacian matrix, sometimes called admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality. It can also be used to construct low dimensional embeddings, which can be useful for a variety of machine learning applications.

Lexicographic product of graphs

In graph theory, the lexicographic product or (graph) compositionGH of graphs G and H is a graph such that

Hypercube graph

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cubical graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n−1n edges, and is a regular graph with n edges touching each vertex.

Hedetniemis conjecture

In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that

In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing (1968), and states that, if γ(G) denotes the minimum number of vertices in a dominating set for G, then

In mathematics, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs G1 and G2 and produces a graph H with the following properties:

Strong product of graphs

In graph theory, the strong productGH of graphs G and H is a graph such that

Trace diagram

In mathematics, trace diagrams are a graphical means of performing computations in linear and multilinear algebra. They can be represented as graphs in which some edges are labeled by matrices. The simplest trace diagrams represent the trace and determinant of a matrix. Several results in linear algebra, such as Cramer's Rule and the Cayley–Hamilton theorem, have simple diagrammatic proofs. They are closely related to Penrose's graphical notation.

Simplex graph

In graph theory, a branch of mathematics, the simplex graph κ(G) of an undirected graph G is itself a graph, with one node for each clique in G. Two nodes of κ(G) are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.

In graph theory, the bipartite double cover of an undirected graph G is a bipartite covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G.

In graph theory, the graph bandwidth problem is to label the n vertices vi of a graph G with distinct integers f(vi) so that the quantity is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

Graph power

In graph theory, a branch of mathematics, the kth powerGk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc.

Hanoi graph

In graph theory and recreational mathematics, the Hanoi graphs are undirected graphs whose vertices represent the possible states of the Tower of Hanoi puzzle, and whose edges represent allowable moves between pairs of states.

Locally linear graph

In graph theory, a locally linear graph is an undirected graph in which the neighborhood of every vertex is an induced matching. That is, for every vertex , every neighbor of should be adjacent to exactly one other neighbor of . Equivalently, every edge of such a graph belongs to a unique triangle . Locally linear graphs have also been called locally matched graphs.

References