Products of graphs¶
This module gathers everything related to graph products. At the moment it contains an implementation of a recognition algorithm for graphs that can be written as a Cartesian product of smaller ones.
References:
Author:
- Nathann Cohen (May 2012 – coded while watching the election of Francois Hollande on TV)
Cartesian product of graphs – the recognition problem¶
First, a definition:
Definition The Cartesian product of two graphs
and
, denoted
, is a graph defined on the pairs
.
Two elements
are adjacent in
if and only if :
and
; or
and
Two remarks follow :
- The Cartesian product is commutative
- Any edge
of a graph
can be given a color
corresponding to the unique index
such that
and
differ.
The problem that is of interest to us in the present module is the following:
Recognition problem Given a graph, can we guess whether there exist graphs
such that
?
This problem can actually be solved, and the resulting factorization is unique. What is explained below can be found in the book Handbook of Product Graphs [HIK11].
Everything is actually based on simple observations. Given a graph , finding
out whether
can be written as the product of several graphs can be attempted
by trying to color its edges according to some rules. Indeed, if we are to color
the edges of
in such a way that each color class represents a factor of
,
we must ensure several things.
Remark 1 In any cycle of
no color can appear exactly once.
Indeed, if only one edge
of a cycle were labelled with color
, it would mean that:
- The only difference between
and
lies in their
th coordinate
- It is possible to go from
to
by changing only coordinates different from the
th
A contradiction indeed.
![]()
That means that, for instance, the edges of a triangle necessarily have the same color.
Remark 2 If two consecutive edges
and
have different colors, there necessarily exists a unique vertex
different from
and incident to both
and
.
In this situation, opposed edges necessarily have the same colors because of the previous remark.
![]()
1st criterion : As a corollary, we know that:
- If two vertices
have a unique common neighbor
, then
and
have the same color.
- If two vertices
have more that two common neighbors
then all edges between the
and the vertices of
have the same color. This is also a consequence of the first remark.
2nd criterion : if two edges
and
of the product graph
are such that
then the two edges
and
necessarily have the same color.
This is a consequence of the fact that for any two verticesof
(where
and
), we have
. Indeed, a shortest path from
to
in
contains the information of a shortest path from
to
in
, and a shortest path from
to
in
.
The algorithm¶
The previous remarks tell us that some edges are in some way equivalent to some
others, i.e. that their colors are equal. In order to compute the coloring we
are looking for, we therefore build a graph on the edges of a graph ,
linking two edges whenever they are found to be equivalent according to the
previous remarks.
All that is left to do is to compute the connected components of this new graph, as each of them representing the edges of a factor. Of course, only one connected component indicates that the graph has no factorization.
Then again, please refer to [HIK11] for any technical question.
To Do¶
This implementation is made at Python level, and some parts of the algorithm
could be rewritten in Cython to save time. Especially when enumerating all pairs
of edges and computing their distances. This can easily be done in C with the
functions from the sage.graphs.distances_all_pairs
module.
Methods¶
-
sage.graphs.graph_decompositions.graph_products.
is_cartesian_product
(g, certificate=False, relabeling=False)¶ Tests whether the graph is a Cartesian product.
INPUT:
certificate
(boolean) – ifcertificate = False
(default) the method only returnsTrue
orFalse
answers. Ifcertificate = True
, theTrue
answers are replaced by the list of the factors of the graph.relabeling
(boolean) – ifrelabeling = True
(impliescertificate = True
), the method also returns a dictionary associating to each vertex its natural coordinates as a vertex of a product graph. Ifis not a Cartesian product,
None
is returned instead.This is set to
False
by default.
See also
sage.graphs.generic_graph.GenericGraph.cartesian_product()
graph_products
– a module on graph products.
Note
This algorithm may run faster whenever the graph’s vertices are integers (see
relabel()
). Give it a try if it is too slow !EXAMPLE:
The Petersen graph is prime:
sage: from sage.graphs.graph_decompositions.graph_products import is_cartesian_product sage: g = graphs.PetersenGraph() sage: is_cartesian_product(g) False
A 2d grid is the product of paths:
sage: g = graphs.Grid2dGraph(5,5) sage: p1, p2 = is_cartesian_product(g, certificate = True) sage: p1.is_isomorphic(graphs.PathGraph(5)) True sage: p2.is_isomorphic(graphs.PathGraph(5)) True
Forgetting the graph’s labels, then finding them back:
sage: g.relabel() sage: g.is_cartesian_product(g, relabeling = True) (True, {0: (0, 0), 1: (0, 1), 2: (0, 2), 3: (0, 3), 4: (0, 4), 5: (5, 0), 6: (5, 1), 7: (5, 2), 8: (5, 3), 9: (5, 4), 10: (10, 0), 11: (10, 1), 12: (10, 2), 13: (10, 3), 14: (10, 4), 15: (15, 0), 16: (15, 1), 17: (15, 2), 18: (15, 3), 19: (15, 4), 20: (20, 0), 21: (20, 1), 22: (20, 2), 23: (20, 3), 24: (20, 4)})
And of course, we find the factors back when we build a graph from a product:
sage: g = graphs.PetersenGraph().cartesian_product(graphs.CycleGraph(3)) sage: g1, g2 = is_cartesian_product(g, certificate = True) sage: any( x.is_isomorphic(graphs.PetersenGraph()) for x in [g1,g2]) True sage: any( x.is_isomorphic(graphs.CycleGraph(3)) for x in [g1,g2]) True
TESTS:
Wagner’s Graph (trac ticket #13599):
sage: g = graphs.WagnerGraph() sage: g.is_cartesian_product() False
Empty and one-element graph (trac ticket #19546):
sage: Graph().is_cartesian_product() False sage: Graph({0:[]}).is_cartesian_product() False