2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ This is a general coalescence product. For the first, you can see coalescence product. $\endgroup$
    – Shahrooz
    Mar 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$ Mar 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$
    – Shahrooz
    Mar 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$ Mar 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$ Mar 16, 2012 at 13:07

3 Answers 3

2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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