In
graph theory, the lexicographic product or (graph) composition of graphs and is a graph such that
* the vertex set of is the
cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
; 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 relations, then the edge relation of their lexicographic product is the corresponding
lexicographic order.
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.
Properties
The lexicographic product is in general
noncommutative: . However it satisfies a
distributive law with respect to disjoint union: .
In addition it satisfies an identity with respect to
complementation: . In particular, the lexicographic product of two
self-complementary graphs is self-complementary.
The
independence number
Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...
of a lexicographic product may be easily calculated from that of its factors :
:.
The
clique number of a lexicographic product is as well multiplicative:
:.
The
chromatic number of a lexicographic product is equal to the
''b''-fold chromatic number of ''G'', for ''b'' equal to the chromatic number of ''H'':
:, where .
The lexicographic product of two graphs is a
perfect graph if and only if both factors are perfect .
References
*.
*.
*
*
*.
External links
*{{mathworld , title = Graph Lexicographic Product , urlname = GraphLexicographicProduct
Graph products