Graph Theory¶
Here we introduce graph theoretical concepts related to Rigidity Theory.
General notions¶
Definition 44 (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 45 (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 46 (\((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_kl_sparse()
is_sparse()
is_tight()
is_kl_tight()
References: [LS08]
Graph extensions¶
Definition 47 (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
Then
is called a \(d\)-dimensional k-extension of \(G\).
PyRigi: k_extension()
one_extension()
zero_extension()
all_k_extensions()
extension_sequence()
Connectivity¶
Definition 48 (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 49 (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 50 (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 51 (separating set)
The set \(U\subset V\) is called a separating set if \(G-U\) is not connected.
In particular, if \(U = \{u,v\}\) then U is called a separating pair.
PyRigi: is_separating_set()
Definition 52 (clique)
A clique of a graph \(G\) is an induced subgraph of \(G\) that is complete.
Coning¶
Definition 53 (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 54 (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()