19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

On Equitable Partitions of the Johnson Graph

Presented by Prof. Vladislav KABANOV
Type: Oral presentation
Track: Representations of Graphs


\documentclass[twoside]{article} \begin{document} \title{On Equitable Partitions of the Johnson Graph} \author{A.\,L.~Gavrilyuk, S.\,V.\,Goryainov, and V.\,V.\,Kabanov} \maketitle The {\it Johnson graph} $J(n,m)$ is the graph whose vertices are all binary vectors of length~$n$ and weight~$m$ and in which any two vectors are adjacent if and only if they differ by exactly two coordinates. A $t-(n,k,\lambda)$-scheme is a set of $k$-element subsets ({\it blocks}) of an $n$-element set such that each of its $t$-element subsets is contained in exactly~$\lambda$ blocks. A {\it perfect coloring} (an {\it equitable partition}) of a graph~$\Gamma$ into~$t$ colors (in what follows, a $t$-coloring) is a partition of the vertex set of~$\Gamma$ into~$t$ classes (colors) $C_1,\dots,C_t$ such that, for any $i,j\in \{1,\dots,t\}$, any vertex from the class~$C_i$ is adjacent to the same number of vertices, namely,~$c_{ij}$ vertices, from the class~$C_j$. The matrix $C=(c_{ij})_{i,j=1,\dots,t}$ is called the parameter matrix of the $t$-coloring. We do not distinguish between colorings obtained by renaming the colors (i.e., by equal permutations of rows and columns of the matrix~$C$). The investigation of perfect colorings of Johnson graphs (and other graphs~\cite{ggk1}) is related to generalizations of some problems from coding theory~\cite{ggk2} and is of independent interest for the theory of distance-regular graphs~\cite{ggk3}, in particular, for the theory of graphs from finite geometries~\cite{ggk4}. Further definitions and the history of the problem can be found in~\cite{ggk4,ggk5}, where the study of 2-colorings of Johnson graphs with small parameters was started. In particular, the question on the existence of a 2-coloring of the graph $J(9,3)$ with matrix $\left ( \begin{array}{cc} 10 & 8 \\ 8 & 10 \end{array} \right )$ was posed in~\cite{ggk5}. In the present research, we answer this question in the negative. {\bf Theorem 1.} {\em The Johnson graph $J(9,3)$ has no $2$-colorings with matrix $\left (\begin{array}{cc} 10 & 8 \\ 8 & 10 \end{array} \right )$.} Let us consider some 2-coloring of the graph $J(n,m)$ (without loss of generality, $2m\le n$) with matrix~$C$. It is known \cite[Assertion~2]{ggk5} that, in this case, the number $c_{11}-c_{21}$ is one of the~$m$ nonprincipal eigenvalues $\theta_k=(m-k)(n-m-k)-k$ of the graph, where~$k=1,\dots,m$. Let $m=3$. If $c_{11}-c_{21}=\theta_1$, then \cite[Theorem~4]{ggk5} there exists a unique coloring; its scheme was given in~\cite[Sect.~2]{ggk5}. If $c_{11}-c_{21}=\theta_3=-3$, then, in view of~\cite[Assertion~3]{ggk5}, the existence of a coloring with this property is equivalent to the existence of a scheme with parameters $2-(n,3,c_{21}(n-2)/(c_{12}+c_{21}))$, and there are known criteria for the existence of such a scheme, see~\cite[Theorem~2]{ggk5}. Finally, in the case $c_{11}-c_{21}=\theta_2$, the authors do not know strong necessary conditions for the existence of a coloring with matrix~$C$. For $n=9$, the following two parameter matrices satisfy the known necessary conditions: $\left (\begin{array}{cc} 10 & 8 \\ 8 & 10 \end{array} \right )$ and $\left (\begin{array}{cc} 6 & 12 \\ 4 & 14 \end{array} \right )$. The nonexistence of the latter was established in~\cite{ggk6}, and the nonexistence of the former is proved in the present study. Thus, the obtained result completes the description (the list of admissible matrices) of 2-colorings of the Johnson graph $J(9,3)$. Note that the methods used in the proof of Theorem~1 allow us to proof a more general result. {\bf Theorem 2.} {\em If $n$ is odd, then the Johnson graph $J(n,3)$ has no $2$-colorings with a symmetric matrix~$C$ such that $c_{11}-c_{21}=\theta_2$.} It is interesting that the analog of Theorem~2 for the case of even~$n$ is not true in the general case: for $n=6$, there exists a coloring with matrix $\left(\begin{array}{cc} 6 & 3 \\ 3 & 6 \end{array}\right)$, which was found in~\cite{ggk7} based on the antipodality of the Johnson graph $J(2m,m)$. For even $n>6$, the problem has not been solved yet. Let us note, however, that~$n$ must be congruent to~2 modulo~4. Therefore, a coloring of the graph $J(10,3)$ with matrix $\left (\begin{array}{cc} 12 & 9 \\ 9 & 12 \end{array} \right )$ is an open case with the smallest number of vertices. \smallskip The first author was supported by the Russian President's grant for young scientist no.~MK-938.2011.1. \begin{thebibliography}{999} \bibitem{ggk1} D. G. Fon-der-Flaass, Perfect 2-colorings of a hypercube. Siberian Math. J. {\bf 48} (2007), no.~4, 740--745. \bibitem{ggk2} I. Yu. Mogil'nykh, On the regularity of perfect 2-colorings of the Johnson graph. Probl. Inf. Transm. {\bf 43} (2007), no.~4, 303--309. \bibitem{ggk3} A. E. Brouwer, A. M.Cohen, and A. Neumaier, {\it Distance-Regular Graphs} (Springer-Verlag, Berlin, 1989). \bibitem{ggk4} B. De Bruyn and H. Suzuki, Intriguing sets of vertices of regular graphs, Graphs Combin. {\bf 26} (2010), no.~5, 629--646. \bibitem{ggk5} S. V. Avgustinovich and I. Yu. Mogil'nykh, Perfect 2-colorings of the Johnson graphs $J(8,3)$ and $J(8,4)$. Diskretn. Anal. Issled. Oper. {\bf 17} (2010), no.~2, 3--19. \bibitem{ggk6} I. Yu. Mogil'nykh, On the nonexistence of some perfect 2-colorings of Johnson graphs. Diskretn. Anal. Issled. Oper. {\bf 16} (2009), no.~5, 52--68. \bibitem{ggk7} I. Yu. Mogil'nykh and S. V. Avgustinovich, Perfect 2-colorings of Johnson graphs $J(6,3)$ and $J(7,3)$. Lect. Notes Comp. Sci. {\bf 5228} (2008), 11--19. \end{thebibliography} \end{document}


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors