Im wondering if there's an existing literature on this binary operation involving graphs wherein you identity $n$ vertices from one graph with $n$ vertices from the other such that the resulting structure is still a graph (no loops and multiple edges). For instance, given two paths $[a,b,c]$ and $[d,e,f]$, letting $a=f$ and $c=d$ produces $C_4$.
-
$\begingroup$ This is a general coalescence product. For the first, you can see coalescence product. $\endgroup$– ShahroozMar 12, 2012 at 6:58
-
$\begingroup$ Thanks, but coalescence as defined in personal-homepages.mis.mpg.de/fatay/preprints/Atay-PRE05.pdf and google.com.ph/… involve the identification of only a single vertex. $\endgroup$– Ken GonzalesMar 12, 2012 at 10:09
-
1$\begingroup$ You are right, but I think it is very important that what do you want from this binary operation? The generalized coalescence is defined by myself but I didn't publish it. Also, I think the Corona product can be helpful for you. But Dear Godsil and McKay can give to you an exact answer. $\endgroup$– ShahroozMar 12, 2012 at 18:33
-
$\begingroup$ I think you need to be more specific about your requirements. When you say there are no multiple edges, do you mean that you ignore multiple edges, or that if you identify $u$ with $a$ and $v$ with $b$, then at most one of $uv$, $ab$ is an edge? I assume you are just ignoring multiple edges. If the two sets are cliques or stable sets, then the operation is clique sum or stable set sum. Otherwise you need to be more specific about what vertex mappings are allowed (i.e. if you are identifying $V_1$ and $V_2$, which bijection you use.) $\endgroup$– Andrew D. KingMar 12, 2012 at 19:02
-
$\begingroup$ Its not clique sum, and google doesnt give me helpful hits on "stable set sum". The number of edges stays the same after the "gluing", and the identification $u=a$ and $v=b$ is allowed if at least one of $uv$ or $ab$ is NOT an edge. If both are edges then a multiple edge results. $\endgroup$– Ken GonzalesMar 16, 2012 at 13:07
3 Answers
Since I cannot add comments, I put this as an answer. I do not know about specific graph-theoretical literature about the operation you describe, but it seems that it can be exhibited as a pushout in a suitable category.
For simplicity, I suppose you consider only undirected graphs.
Take the category where objects are sets equipped with a reflexive and symmetric relation, and where a morphism $h: (A,\alpha)\to(B,\beta)$ is an (ordinary) map of sets $h:A\to B$ that satisfies $\forall a,a'\in A: (a,a')\in\alpha\Rightarrow (ha,ha')\in\beta$.
Then the objects of that category correspond to (undirected simple) graphs and therefore also give a notion of graph homomorphism. Let $1$ be the graph with exactly one vertex and write $n$ for the discrete graph with $n$ vertices. Then, given two graphs $G$ and $H$, choosing $n$ vertices in $G$ and $H$ is the same as giving monomorphisms $n\to G$ and $n\to H$, and your gluing operation is then given as a pushout of $G\leftarrow $n$ \rightarrow H$
Have a look at this:
http://www.win.tue.nl/~hholst/Research%20slides/minimum%20rank.pdf
I think that what van der Holst calls Separations is what you need.
In the book of Lov\'asz
http://www.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf
exposes a graph algebra in the sense that you mentioned.