Generalized degrees and Menger path systems (Q1199423): Difference between revisions

The notion of a Menger path system is generalized to a graph \(G\) having property \(P_{d,m}(G)\): given positive integers \(d\), \(m\), then for each pair of vertices \(x\), \(y\in V(G)\), there are at least \(m\) internally disjoint paths in \(G\) from \(x\) to \(y\) each of which has length at most \(d\). Conditions which ensure the property \(P_{d,m}(G)\) are investigated using the idea of a minimum generalized degree condition, where a graph \(G\) satisfies the minimum generalized degree condition \(\delta_ t(G)\geq s\) if the cardinality of the union of the neighbourhoods of each set of \(t\) vertices is at least \(s\).