Talk:Modular decomposition

Modules as a proper generalization of connected components

I inserted text pointing out why the modules are a proper generalization of connected components, that they preserve some of the properties of connected components (isolation of their subgraph from outside influence), and that, in contrast to connected components, they can be "nested," paving the way for the reader to understand why the decomposition is recursive, rather than just a partition.

In addition to being a nice observation that is often overlooked, it makes it interesting to visitors to the well-traveled page Connected components (graph theory). I inserted a link to our page there.

I retained an alternative description of modules using existential and universal quantifiers. I don't think the redundancy hurts. Also, I didn't want to overwrite a previous editor's work without a consensus about it. Ross m mcconnell (talk) 19:52, 14 August 2010 (UTC)

Introductory section

I changed the introductory section to be more in line with the Wikipedia Manual of Style guidelines at WP:lead Ross m mcconnell (talk) 19:59, 14 August 2010 (UTC)

Section on the modular decomposition tree

I rewrote some of this section, while trying to stay faithful to the approach of the previous editors.

If the recursive definition is used, there is no need to mention strong modules. This concept is used in an alternative non-recursive definition that I wrote but decided against putting in, because it would have overwritten the approach of previous editors. The alternative can be examined at User:Ross m mcconnell/Modular decomposition.

I added that a set of vertices is a module if and only if it is a node, or a union of children of a series or parallel node. To explain this, I had to point out that if X is a module and Y is a subset of X, then Y is a module of G if and only if it is a module of G[X].Ross m mcconnell (talk) 22:31, 14 August 2010 (UTC)

Definition of connected component in terms of non-neighbors is incorrect?

We define a connected component thus:

A set X of vertices is a connected component if every member of X is a non-neighbor of every vertex not in X.

I believe this is incorrect. Consider a graph with three vertices A,B,C and no edges. According to the given definition, {AB} is a connected component, but that is not true according to the definition at Connected component. --Doradus (talk) 14:43, 1 November 2010 (UTC)

Thank you Doradus. See my revision of the statement on Nov 4. Ross m mcconnell (talk) 04:44, 4 November 2010 (UTC)

Looks good! --Doradus (talk) 17:08, 11 November 2010 (UTC)