# Disjoint paths on grid graphs

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.

-
Have you computed $f(G)$ for small $n$? – utdiscant May 5 '12 at 20:51
There is a perfect matching on $G$ when $n$ is even, and a near-perfect matching which includes all but a single vertex when $n$ is odd. – anthus Sep 8 '12 at 5:30
This matching does not actually help, because (as I understand the question) we do not control the pairing of the vertices. We get to choose the vertices, then someone else chooses the pairing, and then we attempt to find disjoint paths for that pairing. If we cannot do this for the given vertices, for any choice of pairing, then $f(G) >= m$. – Hew Wolff Oct 26 '12 at 17:24
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. – Hew Wolff Oct 26 '12 at 18:18

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$.