6
$\begingroup$

Let $f(G)$ be the smallest $m$, such that one can find $2m$ vertices in $G$ with the following property: pair up the vertices in any way, and find $m$ paths that join each pair. Then every set of path constructed will have a intersection. (Is there a name for this graph property?)

I have a feeling this property might be connected to the connectedness of a graph. but for large grid graphs, I can chose many vertices and still find disjoint paths connecting the pairs, when it is only 4 connected.

For a $n\times n$ grid graph $G$, what is $f(G)$?

Edit: I have found the name of the property. A graph is $k$-linked if there exist $2k$ elements, such that there are $k$ disjoint paths that pairs two of them.

  • 1
    The $k$-linked property requires that for *every* $k$ pairs of disjoint vertices, the pairs can be joined by disjoint paths. So if $G$ is not $k$-linked, then f(G) >= k. I'm not sure about the converse.2012-10-26

1 Answers 1

-1

Similar property name is bramble, from Diestel's textbook:

A bramble is a set of mutually touching connected vertex sets in $G$; its order is the minimum number of vertices in a set meeting each member of the bramble.

If you looking for this, for $n\times n$ grid it's $n$.

  • 1
    @ChaoXu, I said, they are similar not equivalent, I don't know how to prove they are equivalent.2012-05-08