What is the Lexicographic Product of Graphs? [Discrete Mathematics]

What is the lexicographic product of graphs? This video defines the lexicographic product of graphs and shows you how to calculate the lexicographic product of two graphs. We will work through examples together as well.

The lexicographic product is a binary graph operation; that is, it takes as its input two simple undirected graphs, G and H, and outputs a new simple undirected graph, called the lexicographic product of G and H. The vertex set of this new graph is the cartesian product of the vertex sets of G and H, and vertices are connected to each other according to the adjacency rules outlined in the video.

The lexicographic product is one of the 'big four' graph products, along with the tensor, cartesian, and strong products. It has some interesting properties, namely that the independence, clique, and chromatic numbers of a lexicographic product can easily be found from those of its factor graphs. Unlike the other 'big four' graph products, the lexicographic product of graphs is generally noncommutative.

*******************************************************************************************************
If you want to learn more about graph products, I highly recommend the following book:
"Handbook of Product Graphs": https://amzn.to/3HjF5D8

Note: This is my Amazon Affiliate link. As an Amazon Associate I may earn commissions for purchases made through the link above.

#graphtheory
#vitalsine