Caminos disjuntos en gráficos de red

Question

Deje $f(G)$ ser el más pequeño $m$, de tal manera que uno puede encontrar $2m$ vértices en $G$ con la siguiente propiedad: el par hasta los vértices de cualquier manera, y encontrar $m$ senderos que unen cada par. A continuación, cada conjunto de ruta construido tendrá una intersección. (Hay un nombre para este gráfico de la propiedad?)

Tengo la sensación de que esta propiedad puede ser conectado a la conexión de un gráfico. pero para la gran cuadrícula gráficos, me puede elegir muchos vértices y todavía encontrar distintos caminos que conectan los pares, cuando está a sólo 4 conectado.

Para un $n\times n$ cuadrícula gráfico de $G$, lo $f(G)$?

Edit: he encontrado el nombre de la propiedad. Un grafo es $k$-linked si no existe $2k$ elementos, de tal manera que no se $k$ distintos caminos que une a dos de ellos.

Answer 1

Nombre de característica similar es bramble, de libro de texto de Diestel:

Una zarza es un conjunto de conjuntos de vértices conectados mutuamente tocando en $G$; su orden es el número mínimo de vértices de un conjunto de reuniones a cada miembro de la zarza.

Si usted esta buscando, para la rejilla de $n\times n$ es $n$.