Properties of Markovian subgraphs of a decomposable graph

Abstract

We explore the properties of subgraphs (called Markovian subgraphs) of a decomposable graph under some conditions. For a decomposable graph G and a collection γ of its Markovian subgraphs, we show that the set χ(G) of the intersections of all the neighboring cliques of G contains ∪g∈γχ(g)- We also show that χ(G) = ∪g∈γχ(g) holds for a certain type of G which we call a maximal Markovian supergraph of γ. This graph-theoretic result is instrumental for combining knowledge structures that are given in undirected graphs. © Springer-Verlag Berlin Heidelberg 2006.