Graph Theory¶

Here we introduce graph theoretical concepts related to Rigidity Theory.

General notions¶

Definition 36 (Union)

Let \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) be simple graphs. The union of \(G_1\) and \(G_2\) is the simple graph whose vertex set is \(V_1 \cup V_2\) and whose edge set is \(E_1 \cup E_2\).

PyRigi: __add__()

Sparse and tight graphs¶

Definition 37 (\((k, \ell)\)-sparse and \((k, \ell)\)-tight)

Let \(G = (V, E)\) be a (multi)graph and let \(k, \ell \in \NN\). The graph \(G\) is said to be \((k, \ell)\)-sparse if every set of \(n'\) vertices with \(k\leq n' \leq |V|\) spans at most \(kn' - \ell\) edges. The graph \(G\) is said to be \((k, \ell)\)-tight if it is \((k, \ell)\)-sparse and \(k|V| - \ell = |E|\).

PyRigi: is_sparse() is_tight()

References: [LS08]

Graph extensions¶

Definition 38 (k-extension)

Let \(d,k \in \NN\). Let \(G=(V,E)\) be a graph, let \(F \subset E\) with \(|F|=k\) and let \(v \notin V\). Let \(H=(W,F)\) be the subgraph of \(G\) induced by \(F\). Let further \(S \subset V\) be a set of vertices such that \(S \cap W= \emptyset\) and \(|S|+|W|=d+k\). We define

\[\begin{equation*} E_v = \bigl\{ \{v,u\} : u \in W \cup S \bigr\} \,. \end{equation*}\]

Then

\[\begin{equation*} G'= \bigl( V \cup \{v\}, (E \setminus F) \cup E_v \bigr) \end{equation*}\]

is called a \(d\)-dimensional k-extension of \(G\).

PyRigi: k_extension() one_extension() zero_extension() all_k_extensions() extension_sequence()