✦ LIBER ✦

The maximal size of graphs with at most k edge-disjoint paths connecting any two adjacent vertices

✍ Scribed by Mao-cheng Cai

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 502 KB
Volume: 85
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90161-a

No coin nor oath required. For personal study only.

✦ Synopsis

Let n and k be positive integers satisfying k + 1 s n s 3k -1, and G a simple graph of order n and size e(G) with at most k edge-disjoint paths connecting any two adjacent vertices. In this paper we prove that e(G) s l(n + k)*/8], and give complete characterizations of the extremal graphs and the extremal minimally k-edge-connected graphs.