Neighboring Configurations

In order to design a systematic way to determine which neighboring RPDAGs arise from the inclusion or the removal of an edge in an RPDAG, it is sufficient to consider some local parameters of the two nodes to be connected. First, some additional notation is introduced. If $\vert\cdot\vert$ represents the cardinality of a set, given a node $x$ in a PDAG $G$, we define:

• $p_G(x) = \vert Pa_G(x)\vert$, $\bullet$ $c_G(x) = \vert Ch_G(x)\vert$
• $n_G(x) = \vert Ne_G(x)\vert$, $\bullet$ $a_G(x) = \vert Ad_G(x)\vert$

Observe that for any RPDAG $G$, the following two properties hold:

• $p_G(x)+c_G(x)+n_G(x) = a_G(x)$
• if $p_G(x) \neq 0 \Rightarrow n_G(x)=0$ (hence $p_G(x)+c_G(x) = a_G(x)$)