WikiMili The Free Encyclopedia

In graph theory, the **Cartesian product***G**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.

- the vertex set of
*G**H*is the Cartesian product*V*(*G*) ×*V*(*H*); and - two vertices (
*u,u'*) and (*v,v'*) are adjacent in*G**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 *a* ∈ *A* and *b* ∈ *B*. Products can be specified using set-builder notation, e.g.

The operation is associative, as the graphs (*F**G*) *H* and *F* (*G**H*) are naturally isomorphic. The operation is commutative as an operation on isomorphism classes of graphs, and more strongly the graphs *G**H* and *H**G* are naturally isomorphic, but it is not commutative as an operation on labeled graphs.

In graph theory, an **isomorphism of graphs***G* 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.^{ [1] }

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

- The Cartesian product of two edges is a cycle on four vertices: K
_{2}K_{2}= C_{4}. - The Cartesian product of K
_{2}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 *C _{n}*. The number of vertices in

In the mathematical field of graph theory, a **path graph** or **linear graph** is a graph whose vertices can be listed in the order *v*_{1}, *v*_{2}, …, *v*_{n} such that the edges are {*v*_{i}, *v*_{i+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 graph***L*_{n} is a planar undirected graph with *2n* vertices and *3n-2* edges.

- Thus, the Cartesian product of two hypercube graphs is another hypercube: Q
_{i}Q_{j}= Q_{i+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 K
_{2}C_{n}. - 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.

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:

- (K
_{1}+ K_{2}+ K_{2}^{2}) (K_{1}+ K_{2}^{3}) = (K_{1}+ K_{2}^{2}+ K_{2}^{4}) (K_{1}+ K_{2}),

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

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

- γ(
*G**H*) ≥ γ(*G*)γ(*H*).

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

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.

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 ).

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

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.

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.

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

In graph theory, the **hypercube graph***Q _{n}* is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cubical graph

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 *G*_{1} and *G*_{2} and produces a graph *H* with the following properties:

In graph theory, the **strong product***G* ⊠ *H* of graphs *G* and *H* is a graph such that

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.

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* × *K*_{2}. 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 *v _{i}* of a graph

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.

In graph theory, a branch of mathematics, the *k*th power*G*^{k} 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: *G*^{2} is called the **square** of *G*, *G*^{3} is called the **cube** of *G*, etc.

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.

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.

- Aurenhammer, F.; Hagauer, J.; Imrich, W. (1992), "Cartesian graph factorization at logarithmic cost per edge",
*Computational Complexity*,**2**(4): 331–349, doi:10.1007/BF01200428, MR 1215316 . - Feigenbaum, Joan; Hershberger, John; Schäffer, Alejandro A. (1985), "A polynomial time algorithm for finding the prime factors of Cartesian-product graphs",
*Discrete Applied Mathematics*,**12**(2): 123–138, doi:10.1016/0166-218X(85)90066-6, MR 0808453 . - Hahn, Geňa; Sabidussi, Gert (1997),
*Graph symmetry: algebraic methods and applications*, NATO Advanced Science Institutes Series,**497**, Springer, p. 116, ISBN 978-0-7923-4668-5 . - Imrich, Wilfried; Klavžar, Sandi (2000),
*Product Graphs: Structure and Recognition*, Wiley, ISBN 0-471-37039-8 . - Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008),
*Graphs and their Cartesian Products*, A. K. Peters, ISBN 1-56881-429-1 . - Imrich, Wilfried; Peterin, Iztok (2007), "Recognizing Cartesian products in linear time",
*Discrete Mathematics*,**307**(3-5): 472–483, doi:10.1016/j.disc.2005.09.038, MR 2287488 . - Kaveh, A.; Rahami, H. (2005), "A unified method for eigendecomposition of graph products",
*Communications in Numerical Methods in Engineering with Biomedical Applications*,**21**(7): 377–388, doi:10.1002/cnm.753, MR 2151527 . - Sabidussi, G. (1957), "Graphs with given group and given graph-theoretical properties",
*Canadian Journal of Mathematics*,**9**: 515–525, doi:10.4153/CJM-1957-060-7, MR 0094810 . - Sabidussi, G. (1960), "Graph multiplication",
*Mathematische Zeitschrift*,**72**: 446–457, doi:10.1007/BF01162967, MR 0209177 . - Vizing, V. G. (1963), "The Cartesian product of graphs",
*Vycisl. Sistemy*,**9**: 30–43, MR 0209178 .

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.