Talk:Cartesian product of graphs

Symbol

Example: "...the cartesian product G ◻ H of graphs G and H..."

In my browser, the symbol (the one between G and H in above example) for the cartesian product shows up as mojibake. What is that symbol supposed to be? --kazu (talk) 11:47, 6 November 2008 (UTC)

It is supposed to be a square box. —David Eppstein (talk) 14:37, 6 November 2008 (UTC)

Clarity?

"The operation is essentially commutative, as the graphs G H and H G are naturally isomorphic."

emphasis mine. do these have precise meanings? can someone link to them? i'm assuming that if it's not an informal (ambiguous) statement it's some kind of category-theoretic thing?

disconcision (talk) 02:25, 19 September 2010 (UTC)

It's commutative as an operation on isomorphism classes of graphs. It's not commutative as an operation on labeled graphs. —David Eppstein (talk) 02:30, 19 September 2010 (UTC)

@David Eppstein "it's not commutative as an operation on labeled graphs" I'm looking for a source for this but coming up empty. Do you know where I can find a proof? 2607:9880:1C40:22:A072:C05:9BB9:28D8 (talk) 21:56, 23 August 2022 (UTC)

It's more or less obvious. The labels come out reversed. If $A$ is the one-vertex graph with labeled vertex $a$ and $B$ is the one-vertex graph with labeled vertex $b$, then $A\mathbin {\square } B$ is the one-vertex graph with labeled vertex $(a,b)$ but $B\mathbin {\square } A$ is a different one-vertex labeled graph with labeled vertex $(b,a)$. —David Eppstein (talk) 22:09, 23 August 2022 (UTC)

Reflexive graphs?

I have some doubts that the "cartesian" or box product is the categorical product in the category of reflexive graphs. Two pairs of vertices <a,b> and <a',b'> should be linked by an edge, iff both a and a' as well as b and b' are linked in their respective graphs. Hence the product of a single edge (with two loops at the endpoints) with itself should be a box with both diagonals.

From a categorical perspective the box product of A and B for irreflexive, or not necessarily reflexive graphs is a rather odd construction, while for reflexive graphs (and reflexive directed multi-graphs and for categories) it has a nice description as a pushout of the span AD\tensor B <-- AD\tensor BD -->A\tensor BD, where AD is the discrete reflexive graph underlying A, with just loops at the vertices, and \tensor is the categorical product. Without the requirement of being reflexive, discrete graphs have no edges at all, and the pushout construction collapses to produce just discrete graphs, hence the corresponding operation does not have a unit. What seems to work is the following: if A and B are irreflexive, first make them refelxive by adding all loops, then perform the box product for reflexive graphs (<a,b> and <a',b'> are linked by an edge, iff a and a' as well as b and b' are linked in their respective graphs and at least one of these edges is a distinguished edge), and then eliminate all loops. — Preceding unsigned comment added by 92.76.144.244 (talk) 19:39, 4 September 2014 (UTC)