- Tytuł:
- On Two Generalized Connectivities of Graphs
- Autorzy:
-
Sun, Yuefang
Li, Fengwei
Jin, Zemin - Powiązania:
- https://bibliotekanauki.pl/articles/31342427.pdf
- Data publikacji:
- 2018-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
k -connectivity
pendant tree-connectivity
Cartesian product
Cayley graph - Opis:
- The concept of generalized $k$-connectivity $ \kappa_k (G) $, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity $ \tau_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 $ \kappa_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 $ \kappa_k^' (G) $ and $ \tau_k(G) $ by showing that for a connected graph $G$ of order $n$, if $ \kappa_k^' (G) \ne n − k + 1 $ where $ k \ge 3 $, then $ 1 \le \kappa_k^' (G) − \tau_k (G) \le n − k $; otherwise, $ 1 \le κ_k^' (G) − \tau_k(G) \le 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 $ \tau_k(G) $, where $G$ is a cubic or 4-regular Cayley graph on Abelian groups, $ 3 \le k \le n $.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 245-261
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł