Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
    
This is a general coalescence product. For the first, you can see coalescence product. –  Shahrooz Mar 12 '12 at 6:58
    
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. –  Ken Gonzales Mar 12 '12 at 10:09
1  
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. –  Shahrooz Mar 12 '12 at 18:33
    
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.) –  Andrew D. King Mar 12 '12 at 19:02
    
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. –  Ken Gonzales Mar 16 '12 at 13:07
add comment

2 Answers

up vote 2 down vote accepted

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$

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.