Name
Abstract | ||
|---|---|---|
Let
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S \subseteq V (G)$</tex>
and
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\kappa_{G}(S)$</tex>
denote the maximum number
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex>
of edge-disjoint trees
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T_1, T_2,\ldots, T_r$</tex>
in G such that
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$V \ (T_i) \cap V \ (T_j) =S$</tex>
for any
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$i,j \in \{ 1, 2, \ldots, r\}$</tex>
and
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$i \neq j$</tex>
. For an integer k with
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2 \leq k \leq n$</tex>
, the generalized k-connectivity of a graph G is defined as
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\kappa_k \ (G) = \min \ \{\kappa_{G} \ (S) \vert S \subseteq V (G)$</tex>
and
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert S \vert = k\}$</tex>
. The generalized k-connectivity is a generalization of traditional connectivity. In this paper, we focus on the Cayley graph generated by complete graphs and the Cayley graph generated by wheel graphs, denoted by
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$CT_n$</tex>
and
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$WG_n$</tex>
, respectively. We study the generalized 3-connectivity of the two kinds of graphs and show that
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\kappa_{3} \ (CT_n) = {n(n-1) \over 2} - 1$</tex>
and
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\kappa_3 (WG_n) = 2n - 3$</tex>
for
<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n \geq 3$</tex>
. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1093/computer_journal/bxy054 | Comput. J. |
Keywords | Field | DocType |
generalized connectivity,fault-tolerance,Cayley graph,complete graph,wheel graph | Discrete mathematics,Computer science,Cayley graph,Theoretical computer science | Journal |
Volume | Issue | ISSN |
62 | 1 | 0010-4620 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shu-Li Zhao | 1 | 1 | 4.40 |
| Rongxia Hao | 2 | 165 | 26.11 |