Packing constants in graphs and connectivity

✍ Scribed by Peter Brass

• Book ID: 103059145
• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 82 KB
• Volume: 137
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0135-q

✦ Synopsis

We prove the following theorem: If G is an r-connected graph and there are k vertices of G which have pairwise distance at least d, then G has at least k(rL(d-1)/2J+l)+ ((1 +(-1)a)/2)r vertices. This bound is sharp.

1. For all bounded metric spaces (M,d) and all k~>2 the packing constant d k is defined as dk:= sup inf d(P,Q).