Generalized degrees and Menger path systems

DOI10.1016/0166-218X(92)90132-TMaRDI QIDQ1199423zbMATH OpenOpenAlexFDO

Authors Ralph Faudree, Ronald Gould, Linda Lesniak

Publication date 16 January 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(92)90132-t

zbMATH Keywords

degree condition Menger path system

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

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\).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Generalized degrees and Menger path systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199423)