A graph is k-linked if for every set of 2k distinct vertices {s(1),...,s(k), t(1),...,t(k)} there exist disjoint paths P-1,...,P-k such that the endpoints of P-i are s(i) and t(i). We prove every 6-connected graph on n vertices with 5n - 14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on it vertices with 5n - 15 edges that are not 3-linked for arbitrarily large values of it. (C) 2008 Elsevier Inc. All rights reserved.
The extremal function for 3-linked graphs / R., Thomas; Wollan, PAUL JOSEPH. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 98:5(2008), pp. 939-971. [10.1016/j.jctb.2007.11.008]
The extremal function for 3-linked graphs
WOLLAN, PAUL JOSEPH
2008
Abstract
A graph is k-linked if for every set of 2k distinct vertices {s(1),...,s(k), t(1),...,t(k)} there exist disjoint paths P-1,...,P-k such that the endpoints of P-i are s(i) and t(i). We prove every 6-connected graph on n vertices with 5n - 14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on it vertices with 5n - 15 edges that are not 3-linked for arbitrarily large values of it. (C) 2008 Elsevier Inc. All rights reserved.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
