6
$\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$

3 Answers 3

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$
1
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .