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 module is strong if it does not overlap another module, where two sets overlap when their intersection and both set differences are nonempty. The strong modules form the nodes of the modular decomposition tree.

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


See also

Modular Decomposition, Twin Vertices, Vertex Set

Explore with Wolfram|Alpha

References

Brandstadt, 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