5
$\begingroup$

I wonder if the following simple generalization of Johnson and Kneser graphs has a name? Let the vertex set of the graph $G(n,k,t)$ be the set of $k$-element subsets of an $n$-set, with two $k$-sets adjacent if their intersection has cardinality $t$.

So for $t=0$ we have the Kneser graphs, and for $t=k-1$ we have the Johnson graphs. Does this family of intersection graphs have a name, or a standard notation?

$\endgroup$
2
$\begingroup$

Chen and Lih call such a $G(n,k,t)$ (with the same notation) a uniform subset graph; see "Hamiltonian uniform subset graphs" (1987). As you point out, the Johnson graph $J(n,k)$ is then $G(n,k,k-1)$. And the Kneser graph $KG(n,k)$ corresponds to $G(2n+k,n,0)$.

$\endgroup$
3
$\begingroup$

Well, in one of my favourite books on algebraic graph theory, these graphs are denoted by $J(n,k,t)$ (where you have $G(n,k,t)$, but no name is assigned. I tend to think of them as generalized Johnson graphs. I somehow doubt that Chen and Lih's usage will catch on. I am confident there is no settled naming convention.

$\endgroup$
2
$\begingroup$

Since $G(n,k,0)$ are called Kneser graphs and $G(n,k,k-1)$ are called Johnson graphs, it makes sense to call $G(n,k,t)$ the generalized Kneser graphs or the generalized Johnson graphs. I prefer to refer to $G(n,k,t)$ as the generalized Johnson graphs because then the generalized Kneser graphs can be reserved to refer to the family of graphs $G(n,k, \le s)$. This latter graph is defined to be the graph whose vertices are the $k$-subsets of an $n$-set, with two vertices joined iff the cardinality of their intersection is at most $s$. The special case $s=0$ gives the Kneser graphs, so the terminology generalized Kneser graphs is justified for $G(n,k, \le s$). These graphs have also been studied - for eg, in the papers [Chen and Wang, Discrete Math., 2008] and [Denley, Eur. J. Comb, 1997].

In the literature, the graphs $G(n,k,t)$ have been called the generalized Johnson graphs (see the paper at arxiv.org/pdf/1202.3455.pdf, or the SAGE code on Godsil's website) or uniform subset graphs (see the papers of [Chen and Lih, JCTB, 1987] and [Chen and Wang, Discrete Math., 2008]). I prefer to use the phrase "uniform" to just refer to the fact that the edges of a hypergraph all have the same cardinality (for eg, independent sets in $G(n, k, \le s)$ refer to $k$-uniform $(s+1)$-intersecting families in the set of subsets of an $n$-set). So I now call $G(n,k,t)$ the generalized Johnson graphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.