[Go to site: main page, start]

TOPICS
Search

Graph Module


A graph module of a graph G is a vertex set M such that every vertex outside M is adjacent either to every vertex in M or to no vertex in M. Equivalently, vertices in M have identical neighbors outside M.

A strong module is a graph module that does not overlap another graph module, where two sets overlap when their intersection and both set differences are nonempty. The strong graph modules form the nodes of the modular decomposition tree.

Every singleton set and the full vertex set are graph modules. A class of twin vertices is also a graph module, but a graph module need not consist of pairwise twins.


See also

Modular Decomposition, Modular Decomposition Tree, Strong Module, Twin Vertices, Vertex Set

Explore with Wolfram|Alpha

References

Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, 1999.Habib, M. and Paul, C. "A Survey of the Algorithmic Aspects of Modular Decomposition." Comput. Sci. Rev. 4, 41-59, 2010. https://doi.org/10.1016/j.cosrev.2010.01.001.

Cite this as:

Weisstein, Eric W. "Graph Module." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphModule.html

Subject classifications