Affordable Access

Publisher Website

Enumeration of labelled chain graphs and labelled essential directed acyclic graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
270
Identifiers
DOI: 10.1016/s0012-365x(02)00838-5
Keywords
  • Labelled Directed Acyclic Graph
  • Labelled Chain Graph
  • Labelled Essential Graph
  • Enumeration
  • Bayesian Network

Abstract

Abstract A chain graph is a digraph whose strong components are undirected graphs and a directed acyclic graph (ADG or DAG) G is essential if the Markov equivalence class of G consists of only one element. We provide recurrence relations for counting labelled chain graphs by the number of chain components and vertices; labelled essential DAGs by the number of vertices. The second one is a lower bound for the number of labelled essential graphs. The formula for labelled chain graphs can be extended in such a way, that allows us to count digraphs with two additional properties, which essential graphs have.

There are no comments yet on this publication. Be the first to share your thoughts.