How can a "bridge path" in an undirected graph be defined correctly/mathematically precisely?

87 Views Asked by At

How would you define an undirected graph containing a path solely of bridges like:

Connected Subgraph<->*<->*<->*<->* (* node; <-> undirected edge)

Alternatively: Connected Subgraph<->*<->*<->*<->Connected Subgraph

Where a path of bridges are a number of nodes of degree two starting at a node of higher degree and ending in a node of either degree > 2 or degree one. All edges "inside" (imprecise) the path are bridges. Somehow it will also be necessary to ensure that all nodes in a bridge path have to belong to the same path...

Is there a known precise definition of such a structure in preferably fewer words?

1

There are 1 best solutions below

0
On BEST ANSWER

I do not think there is existing terminology for a "chain of bridges".

There is a related notion of ears (quoted here from Wikipedia):

In graph theory, an ear of an undirected graph $G$ is a path $P$ where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of $P$ has degree two in $G$.

We can take inspiration from this definition, but probably shouldn't build on it, since ears are in practice only used in cases where the two endpoints are in the same connected component.

One possible wording of a definition is:

A $u-v$ path $P$ in a graph $G$ is a bridge path if $P$ is the unique $u-v$ path in $G$, every internal vertex of $P$ has degree $2$ in $G$, and $P$ is not contained in any longer path with these properties.