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 (Sabidussi 1960; Vizing 1963). However, Imrich and 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 (Imrich and Klavžar, Theorem 4.19).
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)}
(Sabidussi 1957). 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).
Read more about this topic: Cartesian Product Of Graphs
Famous quotes containing the word properties:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)