Bounds on path connectivity
type: Item
instance of: scholarly article
title: Bounds on path connectivity
zbMATH Open document ID: 0556.05043
DOI: 10.1016/0012-365X(84)90020-7
author: Alon Itai
author: Avram Zehavi
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: A graph is k-path-connected if it has at least 2k vertices and, for any k pairs of distinct vertices, there are k disjoint paths connecting them. The authors prove a result implying the existence of a function f(d) such that no planar graph of maximum degree d is f(d)-path-connected. For edge-connectivity the following interpolation theorem is proved: Let \(s_ 1,t_ 1,s_ 2,t_ 2\) be vertices such that, for each \(i=1,2\), there are k edge-disjoint paths between \(s_ i\) and \(t_ i\) and let m be any natural number less than k. Then the graph contains a collection of m edge-disjoint paths such that m or \(m+1\) of these connect \(s_ 1\) and \(t_ 1\) and the others connect \(s_ 2\) and \(t_ 2\).
reviewed by: Carsten Thomassen
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 3885950
zbMATH Keywords: path-connected graphs
MaRDI profile type: Publication
cites work: Q4124337
cites work: Q3206972
cites work: On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: Q3718456
cites work: Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
cites work: Disjoint paths in graphs
cites work: Universality considerations in VLSI circuits
cites work: 2-linked graphs
cites work: On the Problem of Decomposing a Graph into n Connected Factors
full work available at URL: 0012-365x(84)90020-7
OpenAlex ID: W2086530778
description: scientific article; zbMATH DE number 3885950