Completely regular codes in the Johnson graphs \(J(v,3)\)
A. Gavrilyuk, S. Goryainov, I. Mogilnykh
The Johnson graph \(J(v,k)\) is a graph whose vertex set
consists of all \(k\)-subsets of a fixed \(v\)-set. Two \(k\)-subsets
are adjacent if and only if they share \(k-1\) elements exactly.
Since the graphs \(J(v,k)\) and \(J(v,v-k)\) are isomorphic, we assume
that \(k\le v/2\). The Johnson graph is distance-regular, see
[1], has diameter \(k\) and \(k+1\) distinct eigenvalues
\(\theta_i = (k-i)(v-k-i)-i,\ i=0,\ldots,k.\)
A perfect coloring with \(r\) colors of a graph \(\Gamma\)
(\(r\)-coloring, for short) is a partition of the vertex set of
\(\Gamma\) into \(r\) parts (colors) \(C_1,\dots,C_r\) such that, for
all \(i,j\in \{1,\dots,r\}\), every vertex in \(C_i\) is adjacent to
the same number of vertices, namely, \(c_{ij}\), in \(C_j\). The
matrix \(C=(c_{ij})_{i,j=1,\dots,r}\) is called the quotient
matrix of a perfect \(r\)-coloring. It is well known
[1] that the eigenvalues of the quotient matrix are
eigenvalues of the graph.
Given a perfect \(r\)-coloring, if an appropriate ordering of its
colors determines a distance partition of the vertex set with
respect to \(C_i\), then \(C_i\) is called a completely regular
code. In this case, the number \(\rho:=r-1\) is called the covering radius of the code.
The set of vertices at maximal distance from a completely regular
code also is a completely regular code and is called the
opposite code [4].
A \(t\)-design is a set \({\cal B}\) of vertices of \(J(v,k)\)
(usually called blocks) such that every \(t\)–subset of \(v\)–set
belongs to the constant number of blocks in \({\cal B}\).
The strength of \({\cal B}\) is the largest \(t\) such that \({\cal B}\) is a
\(t\)-design.
One may show [4] that the strength of a completely regular code of \(J(v,k)\)
is \(t\) such that \(\theta_{t+1}\) is the second largest eigenvalue of the quotient matrix.
Completely regular codes of strength 0 in the Hamming graphs and
Johnson graphs have been described in [3].
Completely regular codes of strength 1 with the assumption that a code
or its opposite induces a disconnected subgraph in \(J(v,k)\) have
been described in [4]. Completely regular codes with
covering
radius 1 in \(J(v,k)\) for
\(v\leq 8\) or \(k=2\) are studied in
[2,5,6].
Given a completely regular code in \(J(v,k)\), the inequality \(t+\rho\leq k\) holds [1],
where \(t\) is its strength, and \(\rho\) is its covering radius.
We also recall, see [2], that any \((k-1)\)-design is
a completely regular code in \(J(v,k)\). Hence, for \(k=3\),
the parameters \((t,\rho)\in \{(1,1),(1,2)\}\) remain unsolved.
Completely regular codes in \(J(v,3)\) with \((t,\rho)=(1,1)\) and
under the assumption that the quotient matrix is symmetric or \(v\) is even
have been classified in [7].
In the present work, we finish the classification of completely regular codes in \(J(v,3)\).
Theorem. The quotient matrix of a perfect \(2\)-coloring that corresponds to
a completely regular code of strength \(1\) and radius \(1\) in
\(J(v,3)\) is one of the following:
\[
\left (
\begin{array}{cc}
3(v-5) & 6\\
4(\textstyle\frac{v}{2}-2) & v-1
\end{array}
\right ),
\left (
\begin{array}{cc}
3(\textstyle\frac{v}{2}-3) & \textstyle\frac{3v}{2}\\
\textstyle\frac{v}{2}-2 & \textstyle\frac{5v}{2}-7
\end{array}
\right ),
\left (
\begin{array}{cc}
3(\textstyle\frac{v}{2}-1) & 3(\textstyle\frac{v}{2}-2)\\
\textstyle\frac{v}{2}+4 & \textstyle\frac{5v}{2}-13
\end{array}
\right ),
\]
in particular, \(v\) is even. Conversely, for any of the matrices
above, there is a perfect \(2\)-coloring of \(J(v,3)\) with
corresponding quotient matrix.
Conclusion. Recently, there have been several results on the
perfect colorings of various graphs, utilizing the local structure
of the graphs [5,7,8]. In this work, using the approach, we obtain
the classification of completely regular codes in \(J(v,3)\) with
covering radius \(\rho=1\) of strength 1. Moreover, we announce that
the case where \(\rho=2\) in \(J(v,3)\) can be also solved using the
approach.
Acknowledgement. The work is supported by RFBR (project 12-01-31098),
and by the grant of the President of Russian Federation
for young scientists (project MK-1719.2013.1).
References
A. E. Brouwer, A. Neumaier, A. M. Cohen, Distance-regular graphs, Springer-Verlag: Berlin, New-York, Heidelberg (1989).
S. V. Avgustinovich, I. Yu. Mogilnykh, Perfect 2-colorings of the Johnson graphs \(J(8,3)\) and \(J(8,4)\),
Diskretn. Anal. Issled. Oper., 17, N2 (2010), 3–19. (Russian)
A. D. Meyerowitz, Cycle-balanced partitions in distance-regular graphs, J. Combin. Inform. System Sci., 17 (1992), 39–42.
W. J. Martin, Completely regular designs of strength one, J. Algebr. Comb., 3 (1994), 170–185.
I. Yu. Mogilnykh, On the nonexistence of some perfect 2-colorings of Johnson graphs, Diskretn. Anal. Issled. Oper., 16, N5 (2009), 52–68. (Russian)
S. V. Avgustinovich, I. Yu. Mogilnykh, Perfect 2-colorings of
Johnson graphs \(J(6,3)\) and \(J(7,3)\), Lect. Notes Comp. Sci., 5228 (2008), 11–19.
A. L. Gavrilyuk, S. V. Goryainov, On perfect 2-colorings of Johnson graphs \(J(v,3)\), J. of Comb. Designs, (2012). (accepted)
A. L. Gavrilyuk, I. Yu. Mogilnykh, Cameron–Liebler line classes in \(PG(n,4)\), Des. Codes Cryptogr. (2013). (accepted)
