PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 38 | 1 | 245-261
Tytuł artykułu

On Two Generalized Connectivities of Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
The concept of generalized k-connectivity κk(G), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity τk(G) was also introduced by Hager in 1985, which is a specialization of generalized k-connectivity but a generalization of the classical connectivity. Another generalized connectivity of a graph G, named k-connectivity κ′k(G), introduced by Chartrand et al. in 1984, is a generalization of the cut-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of κ′k(G) and τk(G) by showing that for a connected graph G of order n, if κ′k(G) ≠ n − k + 1 where k ≥ 3, then 1 ≤ κ′k(G) − τk(G) ≤ n − k; otherwise, 1 ≤ κ′k(G) ‘− τk(G) ≤ n − k + 1. Moreover, all of these bounds are sharp. We get a sharp upper bound for the 3-connectivity of the Cartesian product of any two connected graphs with orders at least 5. Especially, the exact values for some special cases are determined. Among our results, we also study the pendant tree-connectivity of Cayley graphs on Abelian groups of small degrees and obtain the exact values for τk(G), where G is a cubic or 4-regular Cayley graph on Abelian groups, 3 ≤ k ≤ n.
Wydawca
Rocznik
Tom
38
Numer
1
Strony
245-261
Opis fizyczny
Daty
wydano
2018-02-01
otrzymano
2016-06-16
poprawiono
2016-11-02
zaakceptowano
2016-11-07
online
2017-12-30
Twórcy
autor
autor
autor
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1987
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ć.