# On Two Generalized Connectivities of Graphs

Yuefang Sun; Fengwei Li; Zemin Jin

Discussiones Mathematicae Graph Theory (2018)

- Volume: 38, Issue: 1, page 245-261
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYuefang Sun, Fengwei Li, and Zemin Jin. "On Two Generalized Connectivities of Graphs." Discussiones Mathematicae Graph Theory 38.1 (2018): 245-261. <http://eudml.org/doc/288551>.

@article{YuefangSun2018,

abstract = {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.},

author = {Yuefang Sun, Fengwei Li, Zemin Jin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {k-connectivity; pendant tree-connectivity; Cartesian product; Cayley graph},

language = {eng},

number = {1},

pages = {245-261},

title = {On Two Generalized Connectivities of Graphs},

url = {http://eudml.org/doc/288551},

volume = {38},

year = {2018},

}

TY - JOUR

AU - Yuefang Sun

AU - Fengwei Li

AU - Zemin Jin

TI - On Two Generalized Connectivities of Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2018

VL - 38

IS - 1

SP - 245

EP - 261

AB - 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.

LA - eng

KW - k-connectivity; pendant tree-connectivity; Cartesian product; Cayley graph

UR - http://eudml.org/doc/288551

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.