Has this notion of product of graphs been studied? - MathOverflow

Has this notion of product of graphs been studied?

2010-06-29T23:30:28Z

Let $n\geq 2$ be a positive integer. For the purposes of this definition, let a colored graph be a finite undirected graph in which each edge is colored with one of $n$ colors so that no vertex is incident with two edges of the same color. (Without loss of generality, we suppose that every vertex is incident with exactly one edge of each color; add loops wherever necessary.) If $G_1$ and $G_2$ are two colored graphs, we define a product $H=G_1\times G_2$ as follows.

The vertices of $H$ are the ordered pairs of vertices $(v_1,v_2)$, where $v_i$ is a vertex of $G_i$.
If $(v_1,w_1)$ and $(v_2,w_2)$ are edges of the same color in $G_1$ and $G_2$, respectively, then there is an edge (also of the same color) between $(v_1,v_2)$ and $(w_1,w_2)$ in $H$.

Examples. Consider $n=3$, the simplest interesting case (and the one that interests me most). Let $K'_3$ be the complete graph on three vertices with an extra loop at each vertex, and let $K_4$ be the complete graph on four vertices. (There is essentially only one way to to color each of these graphs.)

$K'_3\times K'_3$ has two components: one is a copy of $K'_3$ and the other has six vertices.
$K'_3\times K_4$ is a connected graph with twelve vertices.
$K_4\times K_4$ has four components, each of which is a copy of $K_4$ .

Does this have a name? Has it been studied? It seems plausible enough to me that this may be a well-studied thing. At the moment, I'm especially interested in necessary/sufficient criteria for the product of connected colored graphs to be connected, or more generally an efficient way to count (or at least estimate) the number of components of the product, but any information that exists is reasonably likely to be useful to me.

My motivation here comes from some problems I'm working on in combinatorial number theory. I have various (colored) graphs that I associate to a positive integer $N$, and in many cases the graph corresponding to $MN$ is the product in this sense of the graphs corresponding to $M$ and $N$ whenever $\gcd(M,N)=1$. The graphs at prime powers are much simpler than the general case.

Answer by David Eppstein for Has this notion of product of graphs been studied?

2010-06-30T05:39:09Z

If these were digraphs with one outgoing edge of each color at each vertex rather than undirected graphs with one incident edge of each color at each vertex, then this construction would be the Cartesian product of deterministic finite automata. It's useful for showing that regular languages are closed under union and intersection.

Answer by Michael Burge for Has this notion of product of graphs been studied?

2010-06-30T06:11:08Z

Section 6.3 in "Algebraic Graph Theory" by Chris Godsil and Gordon Royle covers products of graphs; 6.6 covers colorings of these products. I also vaguely remember a reference to it in Douglas West's "Introduction to Graph Theory" when he was constructing a counterexample to something involving colorings, but it's been too long since I took my Graph Theory course out of that book and I couldn't find it.

Answer by Niel de Beaudrap for Has this notion of product of graphs been studied?

2010-06-30T06:12:20Z

In a similar spirit to David Eppstein's answer, one can relate this construction to the tensor product (a.k.a. the Cartesian product) of graphs and digraphs. If it is a standard construction, I'm not aware of it.

We may represent edge-colourings of the sort you describe by introducing a new node for each edge-colour, subdividing each edge of the original graph, and linking the central vertex of each edge to the appropriate colour-node. (This requires a multi-graph construction if you have loops in the original graph; you could fix this with additional subdivisions if you prefer simple-ish graphs.) If you use directed arcs to the colour nodes, you could use the asymmetry to make this construction reversible, up to permutation of the colours. Let us call this an edge subdivision model of a proper edge-colouring.

The tensor product of graphs G and H is a graph T such that V(T) = V(G) × V(H), and edge-relations { (g₁,h₁), (g₂, h₂) } ∈ E(T) such that {g₁, g₂} ∈ E(G) and {h₁, h₂} ∈ E(H). For digraphs, replace unordered pairs with ordered pairs. In terms of relations on the sets V(G) and V(H), this is the logical conjunction. It is easy to see that in digraphs, only those vertex-pairs (g₁,h₁), (g₂, h₂) which have consistent arc directions for each co-ordinate in the digraphs G and H will have arcs in the tensor product.

The consistency of arc-directions in tensor products of digraphs is what David remarks on in his response: if each node has one inbound arc and one outbound arc, in both graphs, the tensor product will have the same property. But it may be difficult to obtain a well-defined mapping from edge-colours to arc directions, because edge-colours don't have any asymmetry in them. This motivates finding a different way of encoding structural information in an edge than asymmetry --- such as the subdivision models I describe above.

If you take the tensor product of two coloured-subdivision graphs as I describe above, you get a first approximation to (an edge-subdivision model of) the graph construction you describe. There are two defects: (a) it has too many colours, one colour (a,b) for each pair of colours in the original colouring; and (b) it has vertices (v,e) which correspond to a vertex v ∈ V(G) in one co-ordinate and a subdivided edge e ∈ E(H) in another co-ordinate. However, from this tensor product we may easily obtain an induced subgraph, which is an edge-subdivision model of the graph construction you consider.

Eliminating excess colours: the colour-pairs (a,b) will be adjacent to nodes corresponding to the edge-pairs (e_G, e_H) where e_G ∈ E(G) has colour a and e_H ∈ E(H) has colour b. You wish to have only consistent edge-colourings; to do this, simply remove the "mismatched colour" nodes (a,b) for a ≠ b, and any vertex adjacent to them which correspond to edges with mismatched colours. Any remaining node (c,c) for some colour c may be identified as the 'colour node' for c in a new edge-subdivision model for a graph.
Eliminating vertex/edge type-mismatched pairs: in an edge-subdivision model for your construction, we obviously would only want pairs (e_G, e_H) for e_G ∈ E(G) and e_H ∈ E(H) or pairs (v_G, v_H) for v_G ∈ V(G) and v_H ∈ V(H), and no mismatched-type vertices (v,e). Fortunately, the vertex-nodes in the subdivision models are not adjacent to any colour; and so neither are mismatched-type nodes in the tensor product. In fact, mimatched-type vertices are only adjacent to other mismatched-type vertices. So we may restrict to the connected component(s) of the product graph which contains the colour nodes.

So, your construction can be 'simulated' by taking an induced subgraph (in which a pre-determined vertex subset is to be removed) of a tensor product of 'uncoloured' graphs and digraphs. However, I haven't heard of this construction being used before.

[Edit: added the remarks about mismatched-type vertices.]

Answer by Cap Khoury for Has this notion of product of graphs been studied?

2010-06-30T15:41:12Z

An observation I made since posting, which may or may not be on the right track.

Let ${\cal A}_n$ be the "free group on $n$ involutions'', that is $\langle x_1,x_2,\ldots,x_n\rangle/\langle x_1^2,x_2^2,\ldots,x_n^2\rangle$. Then a colored graph as described in the question is just a (finite) set with an ${\cal A}_n$ action. (The vertices are the objects, and the generator $x_i$ sends a vertex $v$ to the vertex connected to $v$ by an $i$-colored edge.)

Then this product operation on graphs corresponds to the usual Cartesian product of ${\cal A}_n$-sets.

However, unless there is some developed theory of the actions of the group ${\cal A}_n$ over and above the general theory of group actions, this is probably not the answer I want.

Answer by Richard Kent for Has this notion of product of graphs been studied?

2010-06-30T23:27:04Z

If you wanted this for directed graphs, I would say this:

As Andy Putman suggests, look at Stallings Inventiones paper "The topology of finite graphs."

A directed graph colored with $n$ colors admits an obvious map to a colored oriented wedge of $n$ circles, $X$ say.

Given two directed colored graphs, the fiber product of the two maps to $X$ may be defined the same way you are defining your product, but where the condition being that there is an edge going from $(a,b)$ to $(c,d)$ colored $m$ if there is an edge from $a$ to $c$ colored $m$ and an edge from $b$ to $d$ colored $m$ (so the orientation is taken into account).

This graph is smaller than yours, but has the advantage of being the pullback of a simple diagram.

I think that you should be able to take care of the undirected case by thinking of each edge of your graph as two edges, one for each orientation, or some such device. There's a nice way to think about this in Gersten's paper "Intersection of finitely generated subgroups of free groups and resolutions of graphs" in the same issue of Inventiones---he talks about "ghost edges."

Answer by Swapnil Bhatia for Has this notion of product of graphs been studied?

2010-07-03T21:33:10Z

Since there is no mention of it, I will make one.

The direct product of graphs $G$ and $H$ is defined like this: $V(G \times H) = V(G) \times V(H)$ and $E(G\times H)$ contains only $((g_1, h_1),(g_2, h_2))$ such that $(g_1, g_2) \in E(G)$ and $(h_1, h_2) \in E(H)$.

In your properly edge colored graphs, if one considers all the pairs of monochromatic subgraphs (i.e., maximal subgraphs all of whose edges are the same color)---one in $G$ and the other in $H$---and takes their direct product, then one gets the same result as your product.

The direct product is well-studied---see the book by Imrich and Klavzar. There are also other products such as the normal (strong) product, lex product, cartesian product, etc. that might also be of interest.