Graph Theory

Here we introduce graph theoretical concepts related to Rigidity Theory.

General notions

Definition 49 (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__()

Definition 50 (t-sum)

Given three graphs \(G=(V,E)\), \(G_1=(V_1,E_1)\), and \(G_2=(V_2,E_2)\), we say that \(G\) is a \(t\)-sum of \(G_1,G_2\) along an edge \(e\) if \(G=(G_1\cup G_2)-e\), \(G_1\cap G_2=K_t\) and \(e\in E_1\cap E_2\).

PyRigi: sum_t()

Sparse and tight graphs

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

Let \(G = (V, E)\) be a multigraph and let \(k, \ell \in \NN\) such that \(0\leq \ell < 2k\). Then \(G\) is said to be \((k, \ell)\)-sparse if every set of \(n'\) vertices spans at most \(\max(0,kn' - \ell)\) edges, or equivalently if every set of \(n'\) vertices with at least one edge spans at most \(kn' - \ell\) edges.

Let \(G = (V, E)\) be a simple graph without loops and let \(k, \ell \in \NN\) such that \(0\leq \ell \leq \binom{k+1}{2}\). The graph \(G\) is said to be \((k, \ell)\)-sparse if every set of \(n'\) vertices with \(n' \geq k\) spans at most \(kn' - \ell\) edges.

A (multi)graph \(G\) is said to be \((k, \ell)\)-tight if it is \((k, \ell)\)-sparse and \(|E| = k|V| - \ell\).

PyRigi: is_kl_sparse() is_sparse() is_tight() is_kl_tight()

References: [LS08], [KM22]

Lemma 6

For simple graphs without loops and with \(0\leq \ell < 2k\) the two sparsity definitions from Definition 51 are equivalent.

Algorithm 2 (Pebble-Game — Basic Idea)

Input: A simple graph \(G\) (possibly with loops), integers \(k>0\) and \(\ell\) with \(0\leq \ell < 2k\)

Output: True or False, whether or not \(G\) is \((k,\ell)\)-sparse resp. \((k,\ell)\)-tight

  1. Start with a new graph \(G'\) on the same set of vertices \(V\), but no edges.

  2. Put \(k\) pebbles on every vertex of \(G'\).

  3. Loop over all edges of \(G\). For an edge \(e\):

    1. If the vertices of \(e\) have together at least \(\ell+1\) pebbles:

      • Add a directed edge to \(G'\) between these vertices and remove one pebble from its starting vertex.

    2. Else:

      • Pick a vertex \(v\) of \(e\) with less than \(k\) pebbles.

      • Try to find a pebble reachable by a path in \(G'\) starting at \(v\).

      • If such a path is found, revert all edges in the path, move the pebble to \(v\) and go to step 3.1 considering \(e\) again.

      • If no such path is found for both vertices of the edge, reject the edge and return False.

  4. If no edge was rejected there are at least \(\ell\) pebbles left. For Sparsity return True. For Tighness return True only if there are exactly \(\ell\) pebbles left.

References: [JH97] [LS08]

Definition 52 (Pebble Digraph)

The graph \(G'\) after running the pebble game algorithm is called the pebble digraph.

Graph extensions

Definition 53 (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()

Definition 54 (2-tree)

A graph is a 2-tree if it can be obtained from a single edge by a sequence of 2-dimensional 0-extensions on adjacent vertices only.

Connectivity

Definition 55 (connected)

In a graph \(G\), two vertices \(u\) and \(v\) are called connected if \(G\) contains a path from \(u\) to \(v\). A graph \(G\) is said to be connected if every pair of vertices in the graph is connected.

Definition 56 (k-connected)

Let \(k\in\NN\) and \(k\geq 1\). A graph \(G\) is \(k\)-(vertex-)connected if it has at least \(k+1\) vertices and it remains connected when at most \(k-1\) vertices are removed. In case \(k=2\) it is called biconnected, and in case \(k=3\) it is called triconnected.

Given a graph \(G\), a \(k\)-(vertex)-connected component of \(G\) is a \(k\)-connected subgraph of \(G\) that is not strictly contained in any other \(k\)-connected subgraph of \(G\).

Definition 57 (local connectivity)

Let \(G = (V,E)\) be a graph and \(u,v\in V\), we use \(\kappa_G(u,v)\) to denote the local connectivity of \(u,v\), which is the maximum number of pairwise internally disjoint paths from \(u\) to \(v\) in \(G\), where two paths are internally disjoint if they do not share any edge.

References: [JV24]

Definition 58 (separating set)

A subset \(U\subsetneq V\) is called a separating set of a graph \(G=(V,E)\) if \(G-U\) is not connected.

In particular, if \(|U| = 2\) then U is called a separating pair.

We say that \(U\) separates the vertices \(u\) and \(v\), or that \(U\) is a \((u,v)\)-separating set, if \(u\) and \(v\) are in different connected components of \(G-U\).

PyRigi: is_separating_set() is_uv_separating_set()

Definition 59 (stable set)

Let \(G = (V, E)\) be a graph. The set \(S \subset V\) is called a stable set of \(G\) if there is no edge \(uv\) in \(G\) such that \(u,v \in S\).

PyRigi: is_stable_set() is_stable_separating_set() stable_separating_set()

Definition 60 (clique)

A clique of a graph \(G\) is an induced subgraph of \(G\) that is complete.

Coning

Definition 61 (Cone graph)

Let \(G=(V,E)\) be a graph. Coning a graph adds a new vertex \(v^*\notin V\) and adds edges \(\{u,v^*\}\) for all vertices \(u\in V\) so that \(E^*=E\cup \{\{u,v^*\}\,:\, u\in V\}\), creating the cone graph \(G*\{v^*\} = (V\cup \{v^*\}, E^*)\).

PyRigi: cone()

Apex Graphs

Definition 62 (Apex graphs)

Let \(G=(V,E)\) be a graph and let \(k\) be an integer. If the removal of some set of \(k\) vertices from \(G\) results in a planar graph, we call \(G\) a \(k\)-apex graph or \(k\)-vertex apex graph. Similarly, if the removal of some set of \(k\) edges from \(G\) results in a planar graph, we call \(G\) a \(k\)-edge apex graph.

Moreover, if one of these properties holds for all choices of \(k\) vertices or edges, we call the graph a critically \(k\)-vertex apex graph or critically \(k\)-edge apex graph, respectively.

PyRigi: is_vertex_apex() is_k_vertex_apex() is_edge_apex() is_k_edge_apex() is_critically_vertex_apex() is_critically_k_vertex_apex() is_critically_edge_apex() is_critically_k_edge_apex()