Problem of the month:
Characterize those simple graphs G with
the following two properties: between each
pair of vertices u and v in
G we have that (1) there exist a pair
of vetex-disjoint
paths, and (2) any set of vertex-disjoint paths
betweeen u and v has at
most two elements.
(Note: simple means no loops and at
most one edge joining any pair of distinct
vertices in the graph. Also, P1,...,Pn
are vetex-disjoint paths between u
and v if they
are paths from u to v and if
no two of them share a vertex except for u,v).
|
