In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the lexicographic product or graph composition of graphs and is a graph such that

• the vertex set of is the cartesian product
  Cartesian product
  In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
  
   ; and
• any two vertices and are adjacent in if and only if either is adjacent with in or and is adjacent with in .

If the edge relations of the two graphs are order relation

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

s, then the edge relation of their lexicographic product is the corresponding lexicographic order

Lexicographical order

In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...

.

The lexicographic product was first studied by . As showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem

Graph isomorphism problem

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...

.

Properties

The lexicographic product is in general noncommutative

Commutativity

In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...

: . However it satisfies a distributive law

Distributivity

In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...

 with respect to disjoint union: .
In addition it satisfies an identity with respect to complementation: .

The independence number of a lexicographic product may be easily calculated from that of its factors :

.

The clique number of a lexicographic product is as well multiplicative:

.