数理解析研究所講究録 1394 巻 2004 年 35-46

35
Completely Regular Codes in Johnson graph北海道大学・理学研究科

吉田瞳 (Hitomi Yoshida)

Graduate school of Mathematics,
Hokkaido University

Introduction

1

In this article, we study completely regular codes in some distance regulargraphs. Completely regular codes were first studied by Biggs [2] and P.
Delsarte [4], but there are not yet many articles on this subject. Recently,
research of completely regular codes has been developing with research of
Terwilliger algebra.

We consider completely regular codes in a distance regular graph. Martin[7] conjectured that for completely regular codes in a distance regular graph,,),hold. On the other hand, Koolen [6] showed,inin $H(D, 2)$ . Furthermore, I conjectured$J(n,d)$ . In order to study this conjecture, in this paper we first classify thecompletely regular codes in Johnson graph $J(4,2)$ , $J(5, 2)$ , $J(6,2)$ , $J(6,3)$ .
$\gamma_{i}\leq\gamma_{+1},\cdot$$\beta_{i}2$$\gamma_{i}<$$\beta_{:+1}$$\beta_{i}>\beta_{i+1}$$\gamma_{i}<\gamma.\cdot+1$$\mathrm{i}+1$$\beta_{i}>\beta_{i+1}$

Distance regular graphs

2

A graph is a pair $=(V, E)$ consisting of a set , referred to as the vertex set
That is,of , and a set of 2-subsets of , referred to as the edge set ofwrite
multipleedges.
Weloops
orundirected,
without
our graphs are
76
is an edge of . The distanceif
if 7 is a vertex of andis the length of a shortest path between ) and .
of two vertices 7,, we write
is called the diameter of . Given$d(\gamma,\delta)=i.$
In particular,
for the set of vertices 7 withvalencyof a vertex 7 is theof.
Thedenotes the set of neighbours
cardinality of. A graph is called regular if each vertex has the same
valency .
$V$$\mathrm{Z}$

$V$

$E$

$\Gamma$$\Gamma-$$\Gamma$$\Gamma$$\gamma\sim\delta$$d(\gamma, \delta)$$\Gamma$$\{\gamma,\delta\}$$\delta$$\delta\in\Gamma$$= \max\{d(\gamma, \delta) |\gamma,\delta\in\Gamma\}$$\Gamma$$\delta$$d$$\in\Gamma$$\Gamma(\delta)=\Gamma_{1}(\delta)$$\Gamma_{i}(\delta)$$\delta$$\Gamma(\gamma)$$k$$k(\gamma)$

38
Definition 2.1 A connected graph $\Gamma=(V, E)$ is said to be a distance regulargraph (DRG) if the numbers$c_{i}=|\Gamma_{i-1}(\gamma)\cap\Gamma$

(S) ,
$|$

(5) , and$a_{i}=|\Gamma_{i}(\gamma)\cap\Gamma$$a_{i}=|\mathrm{r},(7)\cap\Gamma(\delta)$$|$$b_{i}=|\Gamma_{\dot{|}+1}(\gamma)\cap\Gamma(\delta)|$$b_{i}=|\Gamma_{+1}.\cdot(\gamma)\cap\Gamma(\delta)|$are independent of the choices of 7,$\delta\in\Gamma$

with$d(\gamma, \delta)=i.$$\mathrm{y}$The numbers$c_{i}$, : and$a$$b.\cdot$

are said to be the intersection numbers of .
$\Gamma$$\iota(\Gamma)1$$a_{0}b_{0}*$is said to be an intersection array of$a_{d}c_{d}*$$a_{d-1}b_{d-1}c_{d-1}$$a_{1}b_{1}c_{1}$$\Gamma$. Clearly,$b_{0}=k,$ $b_{d}=c_{0}=0,c_{1}=1.$

By counting edges
withcontains points, satisfying$\{\delta, \epsilon\}$$d(\gamma, \delta)$$=i$, $d(\gamma, \epsilon)=i+1$ , we see that$k\dot{.}$$k_{\dot{\iota}}$$k_{0}=1$, $k_{1}=k$ ,$k_{:+1}=k_{i}b_{i} \int c_{i+1}$$(i=0, \ldots,d-1)$ ;therefore, the total number of vertices is$\nu=1+k_{1}+\cdots+k_{d}$By counting edges$\{\delta, \epsilon\}$.

with $d(\gamma,\delta)=1,$, wevve see that$\mathrm{d}(\mathrm{i},5)=1$$k=a:+b_{}+$ q..

Examples.
Exmples.

$(\mathrm{i})\mathrm{T}\mathrm{h}\mathrm{e}$polygons; they have intersection array$\Gamma_{i}(\gamma)$

37$0\ldots 01\ldots 11\ldots 1$$20*$$c_{d}0*\}$,where $c_{d}=2$ for the $2d$-gon and $c_{d}=1$ for the ( $2d+$ l)-gon.
(\"u)The five Platnic solids; they have intersection array$\{\begin{array}{l}*\mathrm{l}023*\end{array}\}$(tetrahedron),$\{\begin{array}{lll}*1 2 502 2 052 1* \end{array}\}$

3

$\{$

$21140\}*$$0$(icosahedron),($\mathrm{o}\mathrm{c}\mathrm{t}$ahedron),$\{\begin{array}{lll}*1 2 300 0 032 1*\end{array}\}$$\{\begin{array}{lllll}*\mathrm{l} 1 1 2 300 1 \mathrm{l} 0 032 1 1 1* \end{array}\}$(cube)(dodecahedron)Completely regular codes

A code is a set of a non-empty subset of $\Gamma C\ni x$ is said to be a codeword.
The number$C$$\mathrm{S}(\mathrm{C}):=$

m$\mathrm{i}$$\mathrm{d}(\mathrm{x}, y)|x,y\in C$

is called the minimum distance ofas$C$, $x\neq y\}$. The distance of$x\in\Gamma$

to

$C$

is defined$d(x, C):=\min \mathrm{d}(\mathrm{x},y)|y\in
C\}$ ,$d(x,C):=\min\{d(x, y)|y\inC\}$and the number$t=t_{C}= \max\{d(x,|x\in\Gamma\}$$t=t_{C}=\max\{d(x, C)C)|x\in\Gamma\}$

is called the covering radius of C. The subconstituents of
to are the sets$C$

$C_{l}:=\{x\in\Gamma|d(x, C)=l\}$ ;in particular,$\Gamma$with respected38$C_{0}=C,$

Definition 3.1 A code
the numbers$C$$C_{l}\neq$

is said

to be a completely regular code (CRC) if. $=|C_{*-1}$. rl$\Gamma(x)|$$\gamma_{*}$.

.

$\Leftrightarrow l\leq t$$1$,r{x) , and$\alpha_{\dot{*}}=|C_{1}$$=|$ $C.\cdot\cap$$\cap\Gamma(x)|$$\alpha_{*}$$|$.

$\beta.\cdot=|C_{+1}.\cdot\cap/(x)$$=|C_{\dot{|}+1}\cap\Gamma(x)|$$\beta_{1}$$|$are independent of the choices of$x\in C_{i}$.

$c_{0}$The numbers$\gamma.\cdot$,$\alpha\dot{.},\beta_{i}$are said to be an intersection numbers of$\iota(C)=\{_{\beta_{0}}^{*}\alpha_{0}\alpha_{1}\beta_{1}\gamma_{1}$$C$.

$\beta_{t-1}\alpha_{t-1}\gamma_{t-1}\alpha_{t}\}\gamma_{t}*$is said to be an intersection array of . Clearly,$C$$\beta_{t}=)*$$=0.$

By counting edges
with $\mathrm{d}(8, C)=i$ , $\mathrm{d}(8, C)=i+1$ , we see that
contains points, satisjying$\{\delta, \epsilon\}$$\kappa_{i}$$\kappa_{i+1}=\kappa_{i}\beta_{i}/)\mathrm{i}\}1$$(i=0, \ldots,t-1)$ ;therefore, the total number of vertices is$\nu=\kappa_{0}+\kappa_{1}+\cdots+\kappa_{t}$By counting edges$\{\delta,\epsilon\}$with$\mathrm{d}(8, C)=i,\mathrm{w}\mathrm{e}$$k=\alpha_{j}+\beta_{i}+\gamma$.

see that:.

$C_{i}$

33
Theorem 3.1 (Neumaier[8]) For a completely regular code
regular graph with intersection array$\iota(C)=\{_{\beta_{0}}^{*}\alpha_{0}\alpha_{1}\beta_{1}\gamma_{1}$the subset$C_{t}$$\alpha_{t-1}\beta_{t-1}\gamma_{t-1}\alpha_{t}\gamma_{t}*\}$$C$in a connected,

is a completely regular code with intersection array$\iota(C_{t})=\{_{\gamma_{t}}^{*}\alpha_{t}\alpha_{t-1}\beta_{t-1}\gamma_{t-1}$$\alpha_{1}\beta_{1}\gamma_{1}$$1$

Theorem 3.2 (Suzuki[ll,Pr0p0siti0n 2.1]) In distance-regular graph, a code
is a completely regular code.
$\{x\}$

Proof. By definition of distance-regular graph, it is clear.

口.
is a reversal of . So, we consider the case where
We sayWe say that a completely regular code with covering radius in a distanceregular graph is trivial if $|C|\leq 1,$ $|C_{t}|\leq 1$ or all the vertices of are in$C$$C_{t}$$2 \leq|C|\leq\frac{\nu}{2}$$C$$\Gamma$

$C$

.

$t$

$\Gamma$40
Theorem 3.3 (Koolen[6,The0rem15]) Each completely regular codes in, where is a member of one of the following
and
has
$C$

$Yi$

$\mathrm{S}$$\gamma_{i+1}$$\beta_{i}\geq\beta_{i+1}$$\Gamma$$\Gamma$families.

(i)
(ii)
(iii)
(iv)
(v)
(vi)
(vii)
(viii)
(ix)
(x)
(xi)
(xii)
(xiii)
(xiv)
(xv)
(xvi)
(xvii)(xviii)
(xix)
(xx)

(xxi

4

The Hamming graphs, $H(n,d)$ ,the Johnson graphs, $J(n,d)$ ,the Grassmann graphs, $G_{q}(n,d)$ ,the symplectic dual polar graphs on $[C_{d}(q)]$ ,the orthogonal dual polar gmphs on [Cd(q)],the orthogonal dual polar graphs on $[D_{d}(q)]$ ,the orthogonal dual polar graphs on $[^{2}D_{d+1}(q)]$ ,the unitary dual polar graphs on,
the unitary dual polar raphs on $[^{2}A_{2d-1}(r)]$ ,the bilinear forms graphs, $H_{q}(n,d)$ ,the alternating forms graphs,
the Hermitean forms graphs,
the symmerntc bilinear forms graphs,
the quadratic $forms$ graphs,
the folded Johnson raphs,,
cubes,
the folded
the halved cubes,
the Doob graphs, the direct products of Shrikhande graphs and4-cliques,
the half dual polar graphs, $D_{m,m}(q)$ ,the Ustirnenko graphs, which are the distance l-Or-2 graphs ofdual polar graphs on $[C_{d}(q)]$ , andthe Hemmeter graphs, the extended bipartite doubles of the dual
polar graphs on [Cd(q)],$[^{2}A_{2d}(r)]$$g$$\overline{J}(2m, m)$$g$Completely regular codes in Johnson graph$\mathrm{J}(\mathrm{n},\mathrm{d})$Let $X$ be a finite set of cardinality . The Johnson graph of the -sets in$X$ has vertex set, the collection of -sets of $X$ .
wo vertices 7, 6 areadjacent wheneverhas cardinality $d-$ l. The Johnson graph $J(n,d)$
has an intersection array given by
$d$

$n$

$(\begin{array}{l}nd\end{array})$$\gamma\cap\delta$$d$$\mathrm{T}$41$b_{i}=(n-i)(n-d-i)$ ,4.1$\mathrm{o}$$c_{i}=i^{2}$

for$0\leq i\leq d.$Completely regular codes in $J(n, 2)$
A non-trivial CRC in Johnson graph $/(4,2)$ :$–\backslash ------,---(\backslash 3\backslash ,4)\backslash \sim\backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash ’\backslash$$\{\begin{array}{ll}*1 402 041* \end{array}\}$”$\backslash (2,4$

has one of the following intersection arrays.
(i) $|C|=2$’$\backslash --\sim-’\sim\backslash ’\backslash ’\backslash \backslash (14)|$$—-\{2,4)$$\{\begin{array}{l}*2024*\end{array}\}$42(ii) $|C|=3$$\{\begin{array}{l}*2222*\end{array}\}$$\mathrm{o}$A non-trivial CRC in Johnson graph $J(5,2)$ :(1,4 ““、、‘$\rangle$$’\backslash \wedge\prime\prime(1,3\backslash \backslash -\sim’\sim’\backslash \sim\vee\sim\sim’\sim\sim$$\prime\prime\prime’\backslash -\backslash \sqrt\nearrow$$\sim-\sim\sim\sim-\sim\backslash \backslash \sim-\backslash \backslash -\backslash \backslash \backslash \sim\backslash$$\backslash \sim\backslash \sim\backslash ’\backslash \vee\sim\backslash \backslash ’\sim\backslash ’\backslash ’\sim<’\sim\prime\prime\sim\prime\prime\backslash ’,\sim’(\backslash 3,4)$$\prime\prime-’--’-\prime\prime\prime\prime\prime\prime\prime-\cdot--’-\wedge---\prime\prime---arrow\prime^{-(1,5)_{\backslash \sim}^{\backslash }}\backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \sim\backslash \sim\backslash \backslash \backslash \backslash \sim\backslash \sim$(1,2$\{\begin{array}{ll}*\mathrm{l} 403 262* \end{array}\}$$\backslash \backslash .\backslash \backslash ...\backslash \backslash \backslash \backslash \backslash \backslash \sim\backslash \backslash \backslash \backslash \backslash \backslash \backslash =\backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \backslash \sim\backslash \backslash \backslash \backslash -\backslash \prime\prime\prime-\prime\prime-\backslash \backslash \backslash \backslash --\prime\prime\backslash \backslash \prime\prime\backslash ’--\prime_{-}-’\sim----\backslash (\backslash 3’\backslash -\wedge’’\backslash \backslash ’\sim\backslash \vee’\sim\backslash ’\backslash \backslash \backslash ’\backslash \prime\prime\backslash \backslash \backslash \sim\backslash ’\sim\backslash \backslash \sim\backslash \backslash \prime\prime--’--5^{\backslash }\backslash \underline{(}4,5)-\backslash \backslash \backslash ,\backslash ----------arrow-’\backslash ’\backslash ’\backslash \backslash \sim-\sim-\backslash \backslash -arrow$$\backslash \backslash (2.3\backslash \backslash \backslash "---’-’arrow-\vee^{---}\sim\backslash \nearrow^{(2,4}\sim$$’——’arrow’-\prime\prime\prime\prime\prime-$

’

‘...、

$(2,5’-\prime\prime\prime-\prime\prime-$has, up to reversal, one of the following intersection arrays.

43(i) $|C|=4$$\prime_{---}-’-’\backslash -\backslash \sim(\underline{1},\underline{3}-\sim-\sim---------\underline{\sim}-\simeq-\sim-.-<\sim\nearrow\sim\sim\sim-\sim\sim\sim---------------\iota’-----$;$(1,2)_{\backslash }^{=\simeq}\backslash ,\overline{\backslash \backslash }|^{\backslash \backslash },\backslash .\backslash \backslash \backslash -------\sim---\backslash --\backslash --(2,4\backslash \backslash \backslash \backslash \backslash J\backslash \backslash \backslash \backslash \backslash \backslash \backslash \dot{J\backslash }’\backslash _{\prime}-’-\backslash ’\backslash \prime\prime\prime\prime\prime\prime\backslash ’\backslash ’\backslash ’\backslash \prime’\backslash \backslash \prime\prime\backslash ’\backslash ’\backslash \sim\sim\sim\sim-\prime\prime\prime’$$(3,4)|$$\{\begin{array}{l}*2343*\end{array}\}$(1|,5)\Delta (\sim - 1-, -4 - \sim -, -\check \acute \sim -、 -\sim -\tilde -\sim - - \check - \check - \sim - \tilde (\sim 2-\check ,-\sim -‘ \sim ‘\check \sim -\tilde -‘ - f- \near ow - - ‘$(3^{\cdot},5)$–$——-\sim-\vee\backslash -(\sim 4\vee,5)$(ii) $|C|=5$

1,2$arrow\sim\sim_{\sim}$–\sim \sim \sim$\backslash \backslash \sim\backslash \backslash \backslash \sim\sim\backslash \backslash \backslash \backslash \backslash$\sim -\sim \sim \sim \sim$\backslash \backslash \backslash \backslash -arrow--\backslash \sim-\backslash \backslash <-\sim--,--’,\simeq’(" 2,5)\sim$$’\wedge$\prime\prime$(1,5|\backslash \backslash \backslash \sim-7_{\backslash }^{--\sim}--\sim\sim\sim-\backslash --------\backslash \backslash \backslash \vee\backslash \backslash$$’\wedge 0’..-\sim-\backslash ---\backslash \backslash \backslash \backslash \vee\backslash ’\backslash$$,$$\backslash \backslash \sim\backslash$$\sim’\backslash \sqrt$$’.\backslash ----\sim-----\sim---\sim-\sim\sim---\sim\backslash \sim\simrightarrow\prime p\mathrm{o}\backslash$$\{\begin{array}{l}*4224*\end{array}\}$$4,5|$($\prime\prime.--\cdot.-\cdot---,-\cdot-\wedge--\sim---\prime\prime\backslash ’\backslash arrow\backslash -\prime\prime\backslash \backslash \backslash ’\prime\prime-\backslash \backslash \backslash ’\backslash ’\backslash \backslash 1_{\backslash \backslash }^{\mathrm{z}\mathrm{o}\vee}\backslash ’\backslash \backslash -\prime\prime-\sim\backslash ’\backslash ’\sim--\backslash -\vee\backslash \backslash \backslash \backslash \cdot\backslash \backslash .\cdot\backslash -\backslash arrow.’-\backslash \backslash J\sim..’\backslash \backslash \vee------’\backslash (\backslash 1,4_{\backslash }^{\wedge\backslash }\backslash \backslash \backslash .\backslash J_{\vee\backslash }-\backslash \backslash ’\backslash \backslash ’\backslash \backslash \backslash (\prime 1,\theta)-\backslash _{\backslash }\backslash \prime\prime\prime\prime\prime\prime’\backslash \backslash \backslash -\backslash \backslash \sim\backslash ----’\backslash \backslash (\backslash 2,4)\backslash$優$–\prime’J_{---\sim--\sim-}\prime’-\prime\prime-----arrow$(3,4\sim -

二—-‘$=(\backslash 3,5)\backslash$44$\mathrm{o}$A non-trivial CRC in Johnson graph $J(6,2)$ has up to reversal, one of
the following intersection arrays.
(i) $|C|=3$$\{\begin{array}{l}*2068*\end{array}\}$(ii) $|C|=5$,$\{\begin{array}{ll}*2 624 226* \end{array}\}$$\{\begin{array}{l}*2464*\end{array}\}$(ii) $|C|=6$$\{\begin{array}{l}*4246*\end{array}\}$Lemma 4.1 In Johnson graph $J(n,2)_{f}$ if is odd, then there is no nontrivial completely regular codes with $|C|=2.$$n$Proof. For $n=3,$ there is no non-trivial completely regular codes. So, we
may consider the case $n\geq 5.$ If $\mathrm{C}=\{(i,j), (i, k)\}$ , we can take $(i, l)$ , $(j, m)$in , where $(i, l)$ is adjacent $(i,j)$ and $(i, k)$ , $(j, m)$ is adjacent $(i,j)$ , contradiction. So, isn’t a completely regular code. If $\mathrm{C}=\{(i, l), (j,m)\}$ , we cantake $(i,j)$ , $(i, n)$ in , where $(i,j)$ is adjacent $(i, l)$ and $(j, m)$ , $(i, n)$ is adjacent, contradiction. So,
a completely regular code. Therefore,
there is no non-trivial completely regular code with$\mathrm{C}_{1}$$\mathrm{C}$$\mathrm{C}_{1}$$\mathrm{C}\mathrm{i}\mathrm{s}\mathrm{n}’ \mathrm{t}$$(\mathrm{i},\mathrm{j})$$\mathrm{C}$$|\mathrm{C}|=2.$

Lemma 4.2 In a Johnson graph $J(n,2)$ , let $C=\{(1,2)$ , $(2, 3)$ ,, $n)$ , $(n, 1)\}$ Then is a completely regular code in $J(n,2)$ .

$\square$$\ldots$, $(n-$$C$$1$

Proof. For
or 3, is a trivial completely regular code. For $n=4,$ let
be in
C. Since $(i-1, i)$ or $(i,i+1)$ is in ,,Therefore $(i, 7)$ in . Then, the intersention array is$n=\underline{9}$$(\mathrm{i},\mathrm{j})$$\mathrm{C}$$J(n, 2)\backslash$$\mathrm{C}$$\{(\mathrm{i},\dot{\mathrm{y}})$$\mathrm{C})=1.$$\mathrm{C}_{1}$$\{_{2(n-3)}^{*}2$so$\mathrm{C}$$2(n-4)4*\}$ ,is a non-trivial completely regular code.

口$\square$45
4.2$\mathrm{o}$Completely regular codes in$J$(n, 3)

A non-trivial CRC in Johnson graph $J(6,3)$ has one of the followingintersection arrays.
(i) $|C|=2$(ii) $|C|=4$(iii) $|C|=6$(iv) $|C|=8$$\{\begin{array}{l}*1089*\end{array}$7},, 3$8*1$$*27\}$$27*$$6\}*3$$63*$$45\}*$$\langle$$\{\begin{array}{ll}*2 635 362* \end{array}\}$

6
33
6

$*$

(v) $|C|=10$$(_{3}^{6}\mathrm{r}*$6} ,$6\}*3$$63*\}$

フ4$\{\begin{array}{l}*5445*\end{array}\}$$\{\begin{array}{l}*45\end{array}\}$

,

$\{$

$\{\begin{array}{l}*6336*\end{array}\}$$*$References[1] E. Bannai and T. Ito, Algebraic Combinatorics ,$I$,$\mathrm{B}\mathrm{e}\mathrm{n}\mathrm{j}\mathrm{a}\mathrm{m}\mathrm{i}\mathrm{n}/\mathrm{C}\mathrm{u}\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}$California, 1984.

[2] Biggs, N., Perfect codes in graphs, J. Combin. Th. (B) 15 (1973),

289-296.

[3] A. E. Brouwer, A. M. Cohen and A. Neumaier,
Graphs, Springer Verlag, Berlin, Heidelberg, 1989.

Distance-Regular[4] Delsarte, Ph., An algebraic approach to the association scheme, Philips. Reports 32 (1977), 373-411.
${\rm Res}$[5] A. Jurisic, and J. Koolen and P. Terwilliger, Tight distance-regulargraphs, J. Alg. Combin. 12 (2000), 163-197.

48[6] J. H. Koolen, On a Conjecture of Martin on the Parameters of Com-

pletely Regular Codes and the Classification of the Completely Regular
Codes in the Biggs-Smith Graph, Linear and Multilinear Algebra. 39(1995), 3-17.

[7] W. J. Martin, Completely regular designs, J. Combin. 6 (1998), 261-273.
[8] A. Neumaier, Completely regular codes, Discrete Math, 106/107 (1992),

353-360.

[9] H. Suzuki, The Terwilliger Algebra associated with a set of vertices ina distance-regular graph, preprint.

[10] H. Suzuki, The geometric girth of a distance-regular graph having cer-tain thin irreducible modules, preprint.

[11] H. Suzuki, On Completely Regular Codes and Related Topics, preprint.