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.

  • 0
    Have you computed $f(G)$ for small $n$?2012-05-05
  • 0
    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.2012-09-08
  • 0
    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$.2012-10-26
  • 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