This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of
mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of
Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles
This article has been
automatically rated by a
bot or other tool because one or more other projects use this class. Please ensure the assessment is correct before removing the |auto= parameter.
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)
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)Jumpowreply
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)Jumpowreply
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)reply
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)reply
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)reply
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)reply
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.
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)reply
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of
mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of
Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles
This article has been
automatically rated by a
bot or other tool because one or more other projects use this class. Please ensure the assessment is correct before removing the |auto= parameter.
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)
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)Jumpowreply
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)Jumpowreply
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)reply
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)reply
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)reply
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)reply
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.
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)reply