Talk:Clique-sum

erm...

In the graph picture, in the 'sum' graph, shouldn't all three turquoise vertices be connected with each other? —Preceding unsigned comment added by 62.167.241.17 (talk • contribs)

No, the clique-sum operation allows some of the clique edges to be deleted as part of the operation. —David Eppstein (talk) 15:08, 14 October 2009 (UTC)

It is not clear... Allows some edges... What edges must be deleted? There is a rule? Or we may choose edges to delete? Jumpow (talk) 18:51, 7 December 2014 (UTC)Jumpow

You may choose. —David Eppstein (talk) 19:01, 7 December 2014 (UTC)

I read James G. Oxley, Matroid Theory, Oxford, NY, 1992 and see ... (page 420): The paired vertices are then identified, as are the corresponding pairs of edges. Finally, all identified edges are deleted. Jumpow (talk) 19:19, 7 December 2014 (UTC)Jumpow

It varies by application. You need the version where you can choose what to delete in most of the graph structure theory results. (The strangulated graph case is an exception: for that one you cannot delete any of the identified edges). For the SPQR tree, usually the version in which one deletes all edges is used. —David Eppstein (talk) 19:46, 7 December 2014 (UTC)

Jumpow is right. This definition of clique sum is irrational because the term "sum" should logically denote set sum of edges, so the common edges cancel. In my experience that is the most useful definition so I think that should be the normal definition. It is certainly the one used by Seymour in his historic paper. If no edges are cancelled, "clique union" is appropriate. Obviously, some people's experience is different (cf. Eppstein) but to avoid confusion, any other use should be clearly defined when used. I suggest putting both definitions and this recommendation into the article. Zaslav (talk) 23:24, 16 April 2016 (UTC)

Afterthought: The article's definition makes sense if the name is partial clique sum. Zaslav (talk) 23:27, 16 April 2016 (UTC)

Google scholar: "Your search - "partial clique sum" - did not match any articles." See also WP:RIGHTGREATWRONGS. —David Eppstein (talk) 23:58, 16 April 2016 (UTC)

Agreed. I'm suggesting an improved term to math/cs people who use it. I think the article has to point out that there are two usages: the strict one (no edges remain) and the weak one. I will add that so people will know there is not one agreed definition. Zaslav (talk) 09:09, 17 April 2016 (UTC)

I think there may actually be three uses: keep all edges, delete all edges, or as part of the operation decide on a subset of edges to keep. I agree that we should make it clearer that the definitions differ among sources rather than trying to pretend it's all the same definition. —David Eppstein (talk) 18:58, 17 April 2016 (UTC)

That should be looked into. I will see when I can do it. Zaslav (talk) 05:39, 20 April 2016 (UTC)

In the meantime I added a paragraph saying so (Special:Diff/715754685) but of course you're welcome to modify or replace it. —David Eppstein (talk) 07:06, 20 April 2016 (UTC)

Two sentences meaning really the same

• strangulated graphs are the graphs that can be formed by clique-sums of cliques and maximal planar graphs without deleting edges
• graphs in which every induced cycle of length four or greater forms a minimal separator of the graph (its removal partitions the graph into two or more disconnected components, and no subset of the cycle has the same property) are exactly the clique-sums of cliques and maximal planar graphs, again without edge deletions

While it seems complicated, the article just states the same thing twice, because strangulated graphs = graphs in which every induced cycle of length four or greater forms a minimal separator of the graph.

Am I right? SyP (talk) 09:32, 30 December 2018 (UTC)

Strangulated means that each induced cycle is a separator. The other sentence requires the induced cycles to be minimal separators. But they do appear to be very similar, and the second sentence is a special case of strangulated that might not be independently interesting. —David Eppstein (talk) 16:43, 30 December 2018 (UTC)