Bounded degrees and prescribed distances in graphs

✍ Scribed by Yair Caro; Zsolt Tuza

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 455 KB
• Volume: 111
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90144-i

✦ Synopsis

Let X = {x1, ., x,,,} and Y= { J'~,. ,y,,_} be two disjoint sets of vertices in a graph G. Then (X, Y) is called an antipodal set-pair ofsize m (m-ASP, for short) if the distance of xi and yj is at most two if and only if i #j. We prove that in a graph of maximum degree k every m-ASP has size m < k(k + I)/2 + 1. This upper bound is nearly best possible since, for every k > 2, there exists a regular graph of degree k, with an m-ASP, m>k(k+l)/2 (and m=k(k+1)/2+1

when k=O or 1 (mod4)).

If the degrees of the xi and y, are bounded above by p and q, respectively, then an m-ASP can exist only for m<(p+qP+' ). We conjecture that this bound ckn be improved to m<(Pi4), and verify this conjecture when the graph satisfies some additional assumptions.

Graphs with large ASPS can also be viewed as variants of antipodal graphs, in which a subgraph (the ASP) has been embedded to obtain a 'polarized' antipodal