Johnson graphs are panconnected

Abstract

For any given $n,m\in \mathbb{N}$ with $m<n$, the Johnson graph $J(n,m)$ is defined as the graph whose vertex set is $V=\{v\mid v\subseteq [n]=\{1,...,n\},|v|=m\}$, where two vertices $v$,$w$ are adjacent if and only if $|v\cap w|=m-1$. A graph $G$ of order $n>2$ is panconnected if for every two vertices $u$ and $v$, there is a $u$-$v$ path of length $l$ for every integer $l$ with $d(u,v)\le l\le n-1$. In this paper, we prove that the Johnson graph $J(n,m)$ is a panconnected graph.

6 pages, 1 figures