Partially Directed Graphs

Why

We can embed the undirected graphs as certain garphs directed graphs.

Definition

Suppose that $G = (V, E)$ is a directed graph. If $(v, w) \in E$ and $(w, v) \in E$ we call $(v, w)$ (and $(w, v)$) and bidirected edge (or undirected edge). In other words, an edge $(v, w) \in E$ is undirected if $(v, w)$ is also in $E$.

If every edge of a directed graph is undirected, then we call the graph undirected. If some edges are an some are not, we call $G$ a partially directed graph.

Notation

Suppose $(V, E)$ is a directed graph. It is common to write $v \to w$ for

\[ (v, w) \in E \text{ and } (w, v) \not\in E. \]

Undirected version

As before, the undirected version (or skeleton) of $G$ is the undirected partially directed graph defined satisfying $u \sim v$ if $u \to v$ or $u \sim v$.

Subgraphs

Given a graph $G = (V, E)$ and a set $A \subset V$, the subgraph of $G = (V, E)$ corresponding to $A$ is the graph denoted $G_{A}$ defined by $(A, E \cap (A \times A)$.

Completeness

Suppose $(V, E)$ is a partially directed graph. In the context of partially directed graphs, the graph is complete if $(u,v) \in E$ or $(v, u) \in E$ for any two vertices $u$ and $v$. A subset $A$ is complete if the subgraph $G_A$ is complete. A complete subset that is maximal (w.r.t. $\subseteq$) is called a clique.