Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  01000100 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
add comment

1 Answer

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

share|improve this answer
Why is bramble equivalent to what I stated, the definition looks related but I don't see how to prove they are equivalent. –  Chao Xu May 8 '12 at 12:38
@ChaoXu, I said, they are similar not equivalent, I don't know how to prove they are equivalent. –  Saeed May 8 '12 at 14:02
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.