PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1995 | 15 | 2 | 167-177
Tytuł artykułu

Stronger bounds for generalized degrees and Menger path systems

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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 internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that $P_{d,m}(G)$ is satisfied have been investigated. In particular, it has been shown, for fixed positive integers t ≥ 5, d ≥ 5t², and m, that if an m-connected graph G of order n satisfies the generalized degree condition δₜ(G) > (t/(t+1))(5n/(d+2))+(m-1)d+3t², then for n sufficiently large G has property $P_{d,m}(G)$. In this note, this result will be improved by obtaining corresponding results on property $P_{d,m}(G)$ using a generalized degree condition δₜ(G), except that the restriction d ≥ 5t² will be replaced by the weaker restriction d ≥ max{5t+28,t+77}. Also, it will be shown, just as in the original result, that if the order of magnitude of δₜ(G) is decreased, then $P_{d,m}(G)$ will not, in general, hold; so the result is sharp in terms of the order of magnitude of δₜ(G).
Słowa kluczowe
Kategorie tematyczne
Wydawca
Rocznik
Tom
15
Numer
2
Strony
167-177
Opis fizyczny
Daty
wydano
1995
otrzymano
1994-10-11
Twórcy
autor
  • Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, U.S.A.
autor
  • Computer and Automation Institute, Hungarian Academy of Sciences, H-111 Budapest, Kende u. 13-17, Hungary
Bibliografia
  • [CL] G. Chartrand and L. Lesniak, Graphs and Digraphs (Prindle Weber & Schmidt Boston 1986).
  • [FGL] R.J. Faudree, R.J. Gould and L. Lesniak, Generalized Degrees and Menger Path Systems, Discrete Applied Math. 37-38 (1992) 179-191, doi: 10.1016/0166-218X(92)90132-T.
  • [FGS] R.J. Faudree, R.J. Gould and R.H. Schelp, Menger Path Systems, J. Combin. Math. Combin. Comp. 6 (1989) 9-21.
  • [FJOST] R.J. Faudree, M.S. Jacobson, E.T. Ordman, R.H. Schelp and Zs. Tuza, Menger's Theorem and Short Paths, J. Combin. Math. Combin. Comp. 2 (1987) 235-253.
  • [O] E.T. Ordman, Fault-tolerant Networks and Graph Connectivity, J. Combin. Math. Combin. Comp. 1 (1987) 191-205.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1014
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.