R. J. Faudree1, R. J. Gould2, R. H. Schelp1
1Memphis State University
2Emory University
Abstract:

For positive integers \(d\) and \(m\), let \(P_{d,m}(G)\) denote the property that between each pair of vertices of the graph \(G\), there are \(m\) openly disjoint paths of length at most \(d\). A collection of such paths is called a \({Menger \; path \; system}\). Minimal conditions involving various combinations of the connectivity, minimal degree, sum of degrees, and unions of neighborhoods of pairs of nonadjacent vertices that insure the existence of Menger path systems are investigated. For example, if for fixed positive integers \(d \geq 2\) and \(m\), a graph \(G\) has order \(n\), connectivity \(k \geq m\), and minimal degree \(\delta > (n – (k – m + 1)(d – 2))/{2} + m – 2\), then \(G\) has property \(P_{d,m}(G)\) for \(n\). Also, if a graph \(G\) of order \(n\) satisfies \(NC(G) > {5n}/(d + 2) + 2m\), then \(P_{d,m}(G)\) is satisfied. (A graph \(G\) satisfies \(NC(G) \geq t\) if the union of the neighborhoods of each pair of nonadjacent vertices is at least \(t\).) Other extremal results related to Menger path systems are considered.

E-mail Alert

Add your e-mail address to receive upcoming issues of Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC).

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;