Filled Graphs
Why
We want to talk about optimally eliminating variables in a system of linear equations.1
Definition
An ordered undirected graph is filled or monotone transitive if all higher neighborhoods induce complete subgraphs. An ordering $\sigma $ of an undirected graph $(V, E)$ is a perfect elimination ordering if the ordered undirected graph $((V, E), \sigma )$ is filled.
Let $G = ((V, E), \sigma )$ be an ordered undirected graph. $G$ is filled if, for all $v \in V$, $w, z \in \adjp(v) \implies \set{w, z} \in E$. Equivalently stated, $G$ is filled if, for all $i < j < k$, $\set{\sigma (i), \sigma (j)} \in E$ and $\set{\sigma (i), \sigma (k)} \in E$ imply $\set{\sigma (j), \sigma (k)} \in E$.
Chordality
If $(V, E, \sigma )$ is a filled graph, then
$(V, E)$ is chordal.
Take the vertex with the lowest index on a
cycle of length greater than three.
Take
- Future editions will expand. For example, this sheet is needed for perfect elimination orderings. ↩︎