In graph theory, a bramble for an undirected graph G is a family of connected subgraphs of G that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in G that has one endpoint in each subgraph. The order of a bramble is the smallest size of a hitting set, a set of vertices of G that has a nonempty intersection with each of the subgraphs.
In graph theory, a bramble for an undirected graph G is a family of connected subgraphs of G that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in G that has one endpoint in each subgraph. The order of a bramble is the smallest size of a hitting set, a set of vertices of G that has a nonempty intersection with each of the subgraphs.
Source: Wikipedia "Bramble (graph theory)" · CC BY-SA 4.0
Share this article: X · Bluesky