Some algebraic aspects of enhanced Johnson graphs

Abstract

Given $n,m \in \mathbb{N}$ with $ m < n $ and Let $I=\{1,...,n\}$. The Johnson graph $J(n,m)$ is defined as the graph whose vertex set is $V=\{v\mid v\subseteq I, |v|=m\}$ and two vertices $v$,$w$ are adjacent if and only if $|v\cap w|=m-1$. Let $n=2m$. The enhanced Johnson graph $EJ(2m,m)$ is the graph whose vertex set is the vertex set of $J(2m,m)$ and the edge set is $E_2=E\cup E_1$ where $E$ is the edge set of $J(2m,m)$ and $E_1=\{\{v,v^c\} | v\subseteq I, |v|=m\}$ and $ v^c$ is the complement of the subset $v$ in the set $I$. In this paper, we show that the diameter of $EJ(2m,m)$ is $\lceil\frac{m}{2}\rceil$ (whereas the diameter of $J(2m,m)$ is $m$). Also, we determine the automorphism group of $EJ(2m,m)$ and we show that $EJ(2m,m)$ is an integral graph, namely, every its eigenvalue is an integer. Although, some of our results are special cases of Jonse[7], unlike his proof that used some deep group-theoretical facts, ours usesno heavy group-theoretic facts.