Bounded degrees and prescribed distances in graphs (Q686447)

Two disjoint vertex sets \(X=\{x_ 1,\dots,x_ m\}\) and \(Y=\{y_ 1,\dots,y_ m\}\) of the same cardinality \(m\) are said to form an antipodal set-pair of size \(m\) \((m\)-ASP) if \(d(x_ i,y_ i)\geq 3\) and \(d(x_ i,y_ j)\leq 2\) for \(i\neq j\). It is shown that if \((X,Y)\) is an \(m\)-ASP and \(d(x)\leq p\) and \(d(y)\leq q\) hold for all \(x \in X\) and \(y \in Y\) for some natural numbers \(p\) and \(q\), then \(m \leq \min \{ {p+q+1 \choose p},{p+q+1 \choose q}\}\) and it is conjectured that an even tighter bound holds, namely that, \(m\leq{p+q\choose p}\). The authors show that there are graphs for which the bound in the conjecture is sharp. They also prove the conjecture when the graph satisfies some further conditions. It is then shown that in a graph of maximum degree \(k\), the size of an \(m\)-ASP is at most \(k(k+1)/2+1\). Moreover, for every \(k \equiv 0\) or 1 (mod 4) there is a \(k\)-regular graph with an induced \(m\)-ASP of size \(k(k+1)/2+1\), and for \(k \equiv 2\) or 3 (mod 4) there is a \(k\)- regular graph with an \(m\)-ASP of size \(k(k+1)/2\).