TOPICS
Search

Chain Graph


The term chain graph has distinct meanings in graph theory and graphical models.

In graph theory, a chain graph is a bipartite graph G=(X,Y,E) for which the graph neighborhoods of the graph vertices in each part can be linearly ordered by inclusion. Equivalently, a bipartite graph is a chain graph if it contains no induced subgraph isomorphic to 2K_2, the graph consisting of two disjoint graph edges. Chain graphs are also known as difference graphs.

In graphical models, a chain graph represents dependence relations among random variables and may contain both directed and undirected graph edges, but no graph cycle with at least one directed graph edge whose directions are consistent around the cycle. Removing the directed graph edges leaves undirected components of the graph.


See also

Bipartite Graph, Directed Graph, Graph, Undirected Graph

Explore with Wolfram|Alpha

References

Hammer, P. L.; Peled, U. N.; and Sun, X. "Difference Graphs." Disc. Appl. Math. 28, 35-44, 1990. https://doi.org/10.1016/0166-218X(90)90092-Q.Lauritzen, S. L. Graphical Models. Oxford, England: Oxford University Press, 1996.

Cite this as:

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

Subject classifications